容易发现子串有五种形式:$\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)$ 。

代码:Submission #127234490 – Codeforces

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code