乱七八糟的东西|回文自动机学习笔记乱七八糟的东西|回文自动机

回文自动机是一个跟后缀自动机很像的东西qaq
首先关于一个串的回文子串有几个性质
1：一个串 S S S至多只有 ∣ S ∣ |S| ∣S∣个不同的回文子串
2：每次向一个串尾部添加字符，至多产生一个新的回文子串，如果产生新的回文子串，其一定是包含串尾的回文子串中最长的一个
证明了（2）其实就证明了（1）
我们来证一下（2）：
假设我们向串尾添加了一个字符，产生了新的回文子串，那么其一定含串尾，
假设这个新的包含串尾的最长回文子串是这样一部分

文章图片

（蓝色是新添加的字符，红色是新产生的含串尾最长的回文子串，绿色是对称轴）
如果还产生了新的别的回文子串，那他也一定包含串尾，且长度比这个红串小，假设他是棕色的串

文章图片

容易发现，不管棕色的串是否越过对称轴，根据红串回文的性质，在原串中都一定已经存在一个紫色的串和他相同，那他就不是一个新的回文串
证明了这个我们接下来介绍回文自动机
回文自动机（又叫回文树）是一个维护了原串所有回文子串的自动机，他能够识别原串的所有回文子串，统计每种子串的出现次数，也资瓷统计每种的出现位置（我感觉用线段树合并是资瓷的，虽然好像没见过和出现位置相关的题=v=）
他维护的是两棵树（其实我一直觉得这好像不是一个树的结构qaq，可能这样说方便理解？），一棵代表偶数长度的回文串，一棵代表奇数长度
因为和SAM很像，所以要记录当前自动机内的点数，添加完上个字符后保留串尾原串的最长回文子串节点last
然后每个点有trans指针（表示向这个回文串两边添加字符得到的回文串），fail指针（表示从该串前端删去尽量少的字符能得到的回文串，这个和SAM的parent有点像），cnt（在原串出现次数），len（该回文串长度），（出现位置一般不维护）
然后直接讲建自动机吧
0号节点代表偶数串的树根，1号节点代表奇数串的树根
一开始初始化所有trans都是0，fail[0]=1,len[0]=0,len[1]=-1
为啥len[1]=-1这个看下面的构建过程就会发现这是非常自然且优美的
假设我们已经构建好了串S的回文自动机，我们现在要在串尾添加一个字符a
因为一个回文串（len>2）一定是由一个小一点回文串在两边添加字符得到的，我们从last开始，不断尝试S[i-1-len[p]]和S[i]是否相同，若相同，串p就可以向两端加上a变成回文串np，可以发现对于len<=2的回文串，因为len[0]=0,len[1]=-1，我们这样判也能得到要找的回文子串，且因为每次跳fail跳到的都是在前端缩尽可能少的字符，所以得到的就是包含新串Sa串尾a的最长的回文子串（这个地方和SAM挺像的=v=）
如果p原来没有trans[p][a]这个孩子，那么就产生了新的回文串np，对于fail[np]，我们可以从t=fail[p]开始按上述跳p的步骤跳，跳到一个合法的t后，trans[t][a]就是fail[np]（这里又和AC自动机很像）
如果有就np=trans[p][a]
然后last=np，cnt[last]++
然后就建完了qaq
哦对了关于cnt，建树时只会对每个前缀的最长回文后缀cnt++，求真实出现次数的话，要建完后按节点编号从大到小，cnt[fail[p]]+=cnt[p]
回文自动机的题一般都比较裸？有些套路也和SAM很像
最大的好处是代码短呀OvO
粘个板子（BZOJ3676）

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long using namespace std; const int maxn = 310000; const int maxc = 30; int n; char str[maxn]; int S[maxn]; struct Tree { int son[maxn][maxc],fail[maxn],len[maxn],cnt[maxn]; int tot,last; void init() { tot=1,last=0; memset(son[0],0,sizeof son[0]); memset(son[1],0,sizeof son[1]); fail[0]=1,fail[1]=0; len[0]=0,len[1]=-1; } int newnode(int l) { tot++; memset(son[tot],0,sizeof son[tot]); len[tot]=l,fail[tot]=0; return tot; } void extend(const int i) { int p=last,w=S[i],np; while(S[i-1-len[p]]!=w) p=fail[p]; if(!son[p][w]) { np=newnode(len[p]+2); int t=fail[p]; while(S[i-1-len[t]]!=w) t=fail[t]; fail[np]=son[t][w]; son[p][w]=np; } else np=son[p][w]; cnt[last=np]++; } }Tr; int main() { //freopen("tmp.in","r",stdin); //freopen("tmp.out","w",stdout); scanf("%s",str); n=strlen(str); S[0]=-1; for(int i=0; i=2; i--) Tr.cnt[Tr.fail[i]]+=Tr.cnt[i]; ll ans=0; for(int i=2; i<=Tr.tot; i++) ans=max(ans,(ll)Tr.cnt[i]*Tr.len[i]); printf("%lld\n",ans); return 0; }

一些模板题
bzoj2565
回文自动机来回扫预处理一些，枚举XY的断点，用manacher好像也能做
【乱七八糟的东西|回文自动机学习笔记】bzoj2342
发现一个串如果是双倍回文，有
他的长度是4的倍数
他自身是回文串
他的一半也是回文串
建出回文自动机，建出fail树，求出每个回文串长度的一半是否是回文串
用manacher好像也行qaq