Palindromic tree

一个字符串中的回文子串的种类数是$O(n)$的,$n$为字符串长度。因为每在一个串后面加一个字符最多只可能新加一种回文子串。

例如abab有4种回文子串、aabca也有4种回文子串。

一个非常经典的求出一个串的所有回文子串的方法是利用Manacher算法,求出所有极长回文子串,再将找到的回文子串的hash值存起来,按长度顺序枚举每个串,看这个串去掉两头新产生的串是否存在,存在就可以退出,不存在把新串加入集合。

这样就能得到一个$O(n\log n)$的算法,但需要hash的辅助。

可以看出所有的回文子串可以构成一个树的结构,如果$S = \alpha T\alpha$,$\alpha$为任意一字符,就让$T$成为$S$的父亲。除此之外还需要两个辅助的串,分别是偶数长度回文串与奇数长度回文串的根。而上面那个算法就可以看作是自底向上地构造这两棵树。我们这里就称此为“回文树”(Palindromic tree)。

接下来介绍一个不需要使用hash的线性构造回文树的算法:

初始时树由两个根构成,再对每个节点额外存一个对应回文串的长度len[],两个根的长度分别为-1与0。每个节点还需要额外存储一个指针,指向这个回文串的所有后缀中最长的回文子串。

这个算法是增量的,从初始状态开始,一个一个的添加字符。顺带维护上一次添加字符对应节点的位置last,初始为len为-1的节点。

一旦加了一个字符,就看last对应的位置能否产生一个新回文串,如果不行就让last指向它最长的回文后缀对应的节点,不断如此即可找到新回文串对应节点的父亲。

如果对应父亲节点已经存在这样的儿子,就意味着这个字符的加入并没有产生新的一种回文串,否则建立新节点,让父亲节点的对应字符转移到当前这个节点上,还剩一个问题是怎么找新回文串的最长回文后缀对应的节点,这个也只需要沿着父亲节点的最长回文后缀,挨个找每个节点是否有对应这种字符的转移,第一个有的节点的转移就是当前节点的最长回文后缀。

综上,我们就完成了回文树的整个构造,类比后缀自动机,可知构造的时间复杂度为$O(n)$。而且可以发现除去两个根,回文树的节点数即一个串的所有不同的回文子串数量。而且由于构造是增量的,即可以知道一个串的所有前缀的回文子串种类数,每种串的数量也能很容易的统计出来。

(坑)