回文自动机是一种可以存储一个串中所有回文子串的数据结构。

与其他自动机类似，回文自动机也有转移边和失配指针 $fail$ 组成，每个结点都代表一个回文子串。

对于奇数和偶数的回文串，我们分别建立一棵树。一个节点的 $fail$ 指针指向的是这个节点所代表的回文串的最长回文后缀所对应的节点。转移边代表在原结点代表的回文串前后各加一个相同的字符。还需要对每个结点维护回文子串的长度 $len$ 。

两个初始状态分别代表 $-1,0$ 的回文串，分别叫做奇根和偶根。偶根的 $fail$ 指针指向奇根，我们不用管奇根的 $fail$ 指针，因为奇根不可能失配（因为最短的奇数回文串是单个字符串，这显然存在，不可能失配）。

现在假设已经构造完前 $p-1$ 个字符的回文自动机后，现在插入位置为 $p$ 的字符。

从上一个字符结尾的最长回文子串对应的结点开始，一直沿着 $fail$ 走，直到找到一个结点满足 $s_{p}=s_{p-len-1}$ ，就说明这个位置和这个回文串之前的一个字符一样，所以可以构成新的回文串。如果到最后都没找到， $len$ 为 $-1$ ，正好是 $s_{p}=s_{p}$ ，说明没有这个结点，需要特判新建。

我们还需要求出新建的结点的 $fail$ 指针，具体方法和上面的过程类似，不断跳转 $fail$ 指针，从不加新字符的那个回文串开始，就可以找到另一个带着两个新字符的回文串，然后把 $fail$ 指针指到这个字符串即可。如果 $fail$ 没匹配到，那么将它连向长度为 $0$ 的那个结点，显然可以（因为这是所有节点的后缀）。

对于一个字符串 $s$ ，它的本质不同的回文子串个数最多只有 $|s|$ 个（数学归纳法）。所以转移状态数也是 $O(|s|)$ 的。

1.询问本质不同回文子串的个数

状态数 $-2$ （上面代码 $tot-1$ 即可），因为要排除奇根和欧根。

2.回文子串出现次数

上面的 $cnt$ 数组，类似于 $AC$ 自动机的做法，我们 $fail$ 指向的那个节点的字符串一定在现在这个结点的字符串中出现，又因为编号一定是 $fail$ 更小，所以倒着求一遍就好了。

3.最小回文划分

给定一个字符串 $s(1≤|s|≤10^{5})$ ，求最小的 $k$ ，使得存在 $s_{1},…,s_{k}$ ，满足均为回文串，且依次连接后得到的字符串是 $s$ 。

考虑 $dp$ ，记 $dp[i]$ 表示 $s$ 长度为 $i$ 的前缀的最小划分数，考虑只需要枚举第 $i$ 个字符结尾的所有回文串，有 $dp[i]=1+min_{s[j+1]…i ok}(dp[j])$ ，一个字符串最多有 $O(n^{2})$ 个回文子串，所以时间复杂度是 $O(n^{2})$ ，不能通过。考虑优化。

我们有 $s$ 和 $t$ 两个字符串，周期定义为一直循环出现即可，不一定正好出现完整个， $border$ 定义为前缀和后缀一样且不是原串。周期和 $border$ 的关系： $t$ 是 $s$ 的 $border$ ，当且仅当 $|s|-|t|$ 是 $s$ 的周期。

我们还有 $t$ 是回文串 $s$ 的后缀，则 $t$ 是 $s$ 的 $border$ 当且仅当 $t$ 是回文串。画个图，显然。

我们还有 $t$ 是回文串 $s$ 的 $border(|s|≤2|t|)$ ， $s$ 是回文串当且仅当 $t$ 是回文串。如果 $s$ 是回文串，显然根据上面的定理， $t$ 是回文串，如果 $t$ 是回文串，画了一下挺抽象的当然也是显然的。

还有 $t$ 是回文串 $s$ 的 $border$ ，则 $|s|-|t|$ 是 $s$ 的周期， $|s|-|t|$ 为 $s$ 的最小周期，当且仅当 $t$ 是 $s$ 的最长回文真后缀。

还有 $x$ 是一个回文串， $y$ 是 $x$ 的最长回文真后缀， $z$ 是 $y$ 的最长回文真后缀。令 $u,v$ 分别为满足 $x=uy,y=vz$ 的字符串，则有：

$1.|u|≥|v|$ 。

证明： $|u|=|x|-|y|$ ，是 $x$ 的最小周期，同样也是 $y$ 的周期，又因为 $v$ 是 $y$ 的最小周期，所以 $|u|≥|v|$ 。

$2.$ 如果 $|u|＞|v|$ ， $|u|＞|z|$ 。

$3.$ 如果 $|u|=|v|$ ， $u=v$ 。