容易发现子串有五种形式：$\emptyset,\ s,\ s*,\ *t,\ s*t$，前四种可以建立 suffix automaton 后直接统计，关键在于第五种。
本来想在 $t$ 处统计答案串，但是发现此时找 $s$ 就变成了在 fail 树上找，不太能做。所以不妨考虑在 $s$ 处统计答案串。
考虑原串的 suffix automaton 上的 $u$ 号节点，其 endpos 集合为 ${p_1,p_2,\cdots,p_m}$，因为同一个节点上的所有串能匹配的 $t$ 是相同的，所以只需要考虑以 ${p_{1}+2,p_2+2,\cdots, p_m+2}$ 开头的有多少串即可。
这个问题很好解决：建立反串的 suffix automaton，令以 $p$ 为开头的后缀在反串的 suffix automaton 上的节点为 $k_p$，那么匹配 $u$ 个串个数就是 ${k_{p_{1}+2},k_{p_2+2},\cdots, k_{p_m+2}}$ 在反串的 suffix automaton 的 fail 树上到根的路径并包含的节点长度总和，说白了就是虚树。
这个东西就用 set 启发式合并就行，注意到一个 $k_{p}$ 最多合并 $\log n$ 次，每次合并代价为 $\log n$，所以总时间复杂度为 $O(n\log ^2 n)$ 。
0 条评论