PalindromicTree 学习笔记

Recursion语死早...慎入...

感觉noi之后真是太颓废了...刷了一波tc后感觉既没有提高智商，传统题也不会做了...

正好这次bc出了一道palindromic_tree，于是打算学点新科技...

回文树是一种可以资瓷在线插入字符并维护当前串的所有回文子串的数据结构。

具体地，他由两棵树组成，分别表示长度为奇数和偶数的回文串。树的每一个节点代表一个本质不同的回文子串。如果一个串两边各加入同一个字符后得到的新串仍在原串中，那么这个新串的节点就是原来节点的孩子。

另外每个节点有一条后缀链(类似于parent或fail指针)，表示这个串的最长后缀回文子串。

其中两棵树的根节点分别为0和-1，-1是为了方便表示奇回文串的空串。

显然得到回文树后，我们可以[tex]O(n)[/tex]的求出每个回文串出现的次数。

构造方法如下：

使用类似于sam的增量法。每次将一个字符插入。沿着上次插入的字符形成的回文子串节点的后缀链走，直到找到一个节点的前一个字符与插入的字符相同，那么就形成了一个新的回文串。如果这个串已经出现过，不用管他。否则我们新建一个节点即可。他的后缀链我们采用相同的方法沿着后缀链走就可以了。

时间复杂度为均摊[tex]O(n)[/tex]。空间复杂度为[tex]O(nc)[/tex]，[tex]c[/tex]是字符集大小。

其实大体感受一下就是个在两边一起加入字符的后缀自动机...毛子发明的数据结构是厉害啊...