回文自动机。或者叫回文树。这坑我放了一百年没填了。
结构
回文自动机的每个节点都代表一个回文子串。它有两个起始状态：奇根和偶根。它们是奇回文串和偶回文串的起点，不代表实际的字符串。
每条转移边代表在当前的字符串两端加上一个相同的字符（特别的，奇根连出来的第一条边只有一个字母，即单个字母也是奇回文串）。因此每个节点代表的回文串为：从该节点往上读转移边到根，然后再从根读转移边回来，这样组成一个回文串。注意与奇根相连的一条边只算一次。
与其他自动机相同，PAM 也有 fail 指针。每个节点的 fail 指针指向这个节点所代表的回文串的最长回文后缀对应的节点。特殊的，偶根的 fail 指针指向奇根。
构造
我们增量构造 PAM，每次往里塞一个字符。
插入一个字符时，我们从上一个字符为结尾的最长回文子串开始，不断暴力跳 fail 指针，直到找到一个回文串，使得它的上一个字符和我们插入的字符相同。此时我们就可以扩展这个回文串，并且新建节点，即从这个回文串的代表节点上连一条转移边出去。
然后我们需要求出它的 fail 指针。这个也可以暴力跳 fail 来实现。
复杂度
首先我们得知道这玩意有多少个状态。
定理：对于字符串 \(s\)，它的本质不同回文子串个数最多只有 \(|s|\) 个。、
证明考虑数学归纳法。
- 当 \(|s|=1\) 时，显然只有一个子串。
- 当 \(|s|>1\) 时，添加一个字符只会增长最多一个回文串（也就是我们刚才插入字符找到的能扩展的第一个回文串）。为什么？因为所有后面的增长的回文串都是它的 border。
然后是这玩意的复杂度，它是 \(O(n)\) 的。首先别的地方的复杂度都挺对劲的，除了这个暴力跳 fail。
每次加入字符的时候，在上一次的基础上，每次跳 fail 后对应节点在 fail 树上的深度 \(-1\)，而连接 fail 后，深度只会 \(+1\)。我们只加入 \(n\) 个字符，因此也只会上下跳 \(2n\) 次 fail。综上，复杂度线性。
一个实现。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
char s[500010];
int n,cnt=1,len[500010],trie[500010][26],fail[500010],num[500010];
int last;
int getfail(int x,int i){
while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
return x;
}
void build(){
fail[0]=1;len[1]=-1;
int p=0;
for(int i=1;i<=n;i++){
int x=getfail(p,i);
if(!trie[x][s[i]-'a']){
fail[++cnt]=trie[getfail(fail[x],i)][s[i]-'a'];
trie[x][s[i]-'a']=cnt;
len[cnt]=len[x]+2;
}
p=trie[x][s[i]-'a'];
}
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
build();
return 0;
}
应用
- 本质不同回文子串个数
就是节点数减去奇根和偶根。 - 回文子串出现次数：逆序枚举状态，将当前状态的出现次数加到fail指针对应状态的出现次数即可。
- 最小回文划分。oiwiki上很详细了，这里复读一遍。
我们知道一个串的所有回文后缀按长度排序后可以分成 \(\log |s|\) 段等差数列。考虑每次转移一个等差数列。
对于每个节点 \(x\) 额外维护 \(diff_x=len_x-len_{fail_x}\) 表示 \(x\) 代表的串和 \(fail_x\) 代表的串的长度差值，还有一个 \(slink_x\) 表示下一段等差数列的开头（长度最大的点）。它们可以和 fail 指针一起更新。另外记录 \(g_x\) 表示 \(x\) 所在的以 \(x\) 为最大值的一段等差数列的 \(dp\) 值的最小值（如果你要统计方案数，那就是加和）。
\(dp\) 数组可以用 \(g\) 数组更新，考虑更新 \(g\) 数组。\(g_x\) 当然就是 \(g_{fail_x}\) 加上一个什么东西。可以认为是 \(g_{fail_x}\) 代表的所有串向后移动了一个 \(diff_x\) 的距离，那么新增的只有首项，也就是 \(i-len_{slink_x}-diff_x\) 位置的 \(dp\) 值。