回文树

Summary

回文树（回文自动机，PAM）的每个节点恰好对应原串的一个本质不同回文子串，fail 指针指向该回文串的最长回文真后缀，并设偶根、奇根两个初始节点。它逐字符在线构建，总状态数不超过串长，构建复杂度为线性。借助节点与 fail 树结构，回文树能统计本质不同回文串的个数、每个回文串的出现次数等回文相关问题。

参考资料

• 回文树 - OI Wiki

简介

回文树（回文自动机，Palindromic Automaton，PAM）的每个节点恰好对应原串的一个本质不同的回文子串，$\operatorname{fail}$ 指针指向该回文串的最长回文真后缀。它有偶根、奇根两个初始节点。

逐字符在线构建，总状态数为本质不同回文子串个数（不超过 $n$），构建复杂度 $O(n)$。它能统计本质不同回文串个数、每个回文串的出现次数等。

例题

洛谷 P5496 【模板】回文树 / 回文自动机（PAM）

给定一个小写字母字符串（强制在线，每个字符需异或上一次的答案后还原），对每个位置 $i$，求以 $s_i$ 结尾的回文子串个数。