后缀自动机做题技巧

后缀自动机做题技巧

①后缀自动机的总状态数小于\(2n\)，总转移边数小于\(3n\)

②后缀自动机沿着 link 链接跳的总复杂度为\(O(n)\)，构造后缀自动机的总复杂度也是\(O(n)\)

性质：

①插入字符新增子串数：​​len[p]-len[link[p]]​​

②后缀链接：​​link[p]​​​表示的字符串是​​p​​的后缀

③沿着转移数组走，可以得到母串的所有子串。

④沿着后缀链接走，一直得到的是当前点的后缀串。

⑤如果把非clone点的​​cnt[i]​​​值置为1，然后沿着后缀链接的反向边 dfs 一遍，把其子节点的贡献都加到自己身上，最后得到的​​cnt[i]​​就是 i 这个节点所表示的串在母串中出现的总次数。因为子节点的结束下标肯定是跟 i 不同的（除了clone节点），而 i 所表示的字符串是子节点表示字符串的子串，所以把贡献加以来就可以了。

⑥求第 i 个节点所表示串的出现个数（本质相同，位置不同也可）：先将所有非克隆节点的​​cnt[i]​​置为1，然后在后缀树上跑 dfs ，把 i 的子树的贡献加到自己身上即可。

⑦求第 i 个节点所表示串的出现个数（本质相同，位置不同算一个串）：将所有（包括克隆节点）的​​cnt[i]​​置为1即可。

CAD加油！欢迎跟我一起讨论学习算法