回文自动机学习笔记
概述
回文自动机 \((PAM)\)，也叫回文树
可以用 \(O(n)\) 的时间复杂度求出一个字符串的所有回文子串
构建
回文自动机每个节点表示在它的父节点两侧各加上一个儿子字符
每个节点要记录一个 \(fail\) 指针，代表当前节点的最长回文后缀
因为回文串有奇回文串和偶回文串之分
所以回文自动机有两个初始状态 \(-1\) 和 \(0\)
分别代表所有奇回文串的根和所有偶回文串的根
偶根的 \(fail\) 指针指向奇根，而我们并不关心奇根的 \(fail\) 指针
因为奇根不可能失配（奇根转移出的下一个状态长度为 \(1\)，即单个字符。一定是回文子串）
构建的时候采用增量法构建
考虑构造完前 \(p-1\) 个字符的回文自动机后，添加在原串里位置为 \(p\) 的字符
看一下上一次插入的节点左边能否扩展出位置 \(p\) 的字符
如果不能就一直跳 \(fail\) 指针
扩展成功之后建立父子关系
求新的节点的 \(fail\) 指针时由要由父亲节点的 \(fail\) 指针向外扩展
而不能由父亲节点向外扩展
否则一个节点的 \(fail\) 指针就指向自己了
并且这个过程要在建立新点之前
代码
#include<cstdio>
#include<cstring>
#define rg register
const int maxn=5e5+10;
char s[maxn];
int len;
struct PAM{
struct asd{
int ch[28],siz,fail,len;
}tr[maxn];
int cnt;
void build(){
cnt=0;
tr[cnt].fail=1;
tr[++cnt].len=-1;
}
int getfail(rg int da,rg int now){
while(s[now]!=s[now-tr[da].len-1]) da=tr[da].fail;
return da;
}
int insert(rg int lst,rg int now,rg int p){
rg int da=getfail(lst,now);
if(!tr[da].ch[p]){
cnt++;
tr[cnt].fail=tr[getfail(tr[da].fail,now)].ch[p];
tr[cnt].siz=tr[tr[cnt].fail].siz+1;
tr[cnt].len=tr[da].len+2;
tr[da].ch[p]=cnt;
}
return tr[da].ch[p];
}
}pam;
int main(){
scanf("%s",s+1);
len=strlen(s+1);
pam.build();
s[0]=-1;
rg int lat=0,k=0;
for(rg int i=1;i<=len;i++){
s[i]=(s[i]-97+k)%26;
lat=pam.insert(lat,i,s[i]);;
printf("%d ",k=pam.tr[lat].siz);
}
printf("\n");
return 0;
}
例题
P5555 秩序魔咒
对两个字符串分别建立回文自动机
然后分别从奇根和偶根开始进行 \(dfs\) ，求出两个回文自动机重合的部分中 \(len\) 最大的字符串
CF17E Palisection
正难则反
可以用总的回文串的对数减去不相交的回文串的对数
那么答案就是 \(\sum_{i=1}^n以i结尾的回文串个数 \times i 后面的回文串个数\)
以 \(i\) 结尾的回文串的个数就是 \(i\) 所代表的点在 \(fail\) 树上的深度
\(i\) 后面的回文串个数可以把原串反过来用后缀和记录一下
P4287 [SHOI2011]双倍回文
在回文自动机上维护一个 \(trans\) 数组代表长度小于等于 \(\frac{len}{2}\) 的最长回文后缀
求法和 \(fail\) 指针的求法类似
最后统计一下 \(trans\) 数组的贡献即可