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)$。而且可以发现除去两个根，回文树的节点数即一个串的所有不同的回文子串数量。而且由于构造是增量的，即可以知道一个串的所有前缀的回文子串种类数，每种串的数量也能很容易的统计出来。