回文树
回文树,也就是回文自动机,PAM(Palindrome automaton) 是一个处理回文串的有力工具。然而这个东西比SAM简单多了。。
(它可能比 manacher 要强得多?)
回文自动机有两个根,也就是说其实是有两个树的,一个存储长度为奇数的回文串一个存储长度为偶数的回文串。
回文自动机上的每一个节点表示一个本质不同的回文串。也就是说回文自动机上的节点个数就是本质不同的回文串个数。
- 一些定义
-len[p]表示p节点所代表回文串长度
-fail[p]表示p节点的最长回文后缀所在的节点。
-son[p][c]表示p节点代表回文串两边分别加上字母c得到的回文串的节点。
由于回文树的构造方法类似后缀自动机采用增量法,有一个重要的结论:
每次在当前的字符串结尾添加一个字母,如果新增了回文串,那么新增的本质不同回文串必然是添加后的字符串的最长回文后缀这一个。
证明很简单,画图有:
如果最左边的红色和最右边的红色构成的是最长回文后缀,并且有一个更短的后缀,它一定已经出现过了。
同时这也证明了本质不同的回文个数是O(n)的。
构造回文树
首先,初始状态只有两个点,t0,t1分别表示奇数回文串个数和偶数回文串个数。我们有len[t0]=−1,len[t1]=1。因为单个字符也是回文串,相当于是t0两边分别加一个字符,长度变为 1 。我们让它们的 fail 指针指向对方(没什么意义,只是方便,这样做了可以方便得把所有回文串联系起来)。
用 last 表示插入上一个字符后,当前最长回文后缀所在节点的编号。开始是 0 或者 1。当我们插入一个字符,从 last 向上(fail指针)跳,直到第一个位置使得这个回文串的左边一个字符和这个位置的字符相同。这样找到的必然是最长回文后缀。
- 加入我们找到的节点是p插入的字符是c,先检查一下son[p][c]是否存在。如果存在就说明都出现过了,直接结束。否则新建一个节点q并且len[q]=len[p]+2。
- 这个时候要考虑q的 fail 指针。做法就是继续沿着p向上跳,知道找到又一个满足条件的位置。这个就必然是q的最长回文后缀辣。最后更新一下last即可。
复杂度是O(n)但是我不会证。
粘个板子
plaintext
1 | struct PAM { |