题解 P5496 【【模板】回文自动机（PAM）】
功在不舍
·
·
题解
感觉题解们都不太对我这种萌新友好啊
我来一篇带图的题解把。
1.引入：我们来考虑一个问题，怎么求一个串有多少个本质不同的子串？
如果你用暴力枚举子串或者Manacher+hash，都是O(n^2)的太慢了。
他们没有利用到各个回文子串之间的包含关系，所以比较慢。
zzh
回文自动机就是来利用这种关系解决问题O(n)算法
2.回文树
和AC自动机一样，回文自动机也要有一颗树把回文串“串起来”。
我们知道一个长的回文串去掉他的两头，能得到一个短回文串，
我们利用回文字符串这样性质把他们折叠挂在树上。
但是长度为奇数的回文子串 有中心，而长度为 偶数的回文子串没有。
我们要把长度为奇数、偶数的分开挂着。
0代表偶数长度的根，1代表奇数长度的根。
树上的每一个点都代表一个不同的回文子串（不含0，1）
以abbaabba为例子，下面是他的回文树，上面串着所有他的回文串。
挂的同时我们还可以统计各个回文子串的长度。
len[0]=0,len[1]=-1
其他的点深度+1，len就比父节点增加2。
注意这里节点代表的状态和 trie 树不一样。
状态应该从下往上再往下读。
例如8号点代表的回文子串是 bbaabb
注意如果在奇数树上，最顶上的边只能读1次。
这棵树的节点个数-2就是abbaabba本质不同的回文串个数。
3.O(n)构建与fail
我们肯定不能直接暴力把所有回文子串挂上去。
我们用一种类似后缀树的办法 “增量构造”
即利用s[0\ to\ i-1]的回文树，加入s[i]位得到新的回文树。
明显，我们可能会得到一些新的回文子串，考虑怎么把他放到树上。
由于所有新产生的回文子串都是新最长回文子串的回文后缀，且长度应比最长的小，我们可以把他们“翻转”一下，就可以发现他们一定在s[0\ to \ i-1]的回文树里！（即同时也是前缀）
所以插入一个新点，最多只会建立“最长新回文后缀”这么一个节点，保证了回文自动机的点数是O(n)的。
这也告诉我们一个串的本质不同的回文子串最多有n个，由aaaa.....取到，于是问题转化为了怎么把这一个回文串放到树上。
首先，我们可以发现，如果设新产生的回文子串中长度最大的长度为len,则s[i-len+2\ \ to\ \ i-1]（就是掐头去尾）一定也是一个回文串（len=0直接不用管了）。
其次，这个回文串一定是s[0\ to\ i-1]满足s[i-len[x]-1]=s[i]的最长回文后缀 x，否则添头增尾得到的新的回文子串不是最长的。
“最长”“后缀”让我们想到了什么？->AC:fail[x]
类似的，定义fail[x]为x代表的回文子串的最长回文后缀。
假设 以i-1位结束的最长回文子串在cur位置
$while$遍历，当其中第一次遇到$s[i-len[x]-1]==s[i]$时，一定是新的最长回文后缀,如果那一位在回文数上有$s[i]$这个子节点就直接走过去(重复了)，否则就新建一个。（是不是和AC自动机很像）
下图是abbaabba的完整回文自动机。
你可能会疑惑，0、1一个是偶数空，一个是奇数空，他们的$fail$是干嘛的？
考虑$abbac$,加入到$c$的时候，不管你怎么跳$fail$都匹配不上，但是它 会在奇数根1下面挂上，表示单独的字符C。
$fail[0]=1$ 结合上面的图你可以发现，当出现我说的情况时，fail最后会从奇数根下面的某一位 跳到0，若0也不能增加，就得跳到1去了(奇数根一定可以挂，想想为什么)，让0指向1，就实现了增添新的单独字符的功能。
你可能又会问了，这样不是跳了两次吗，为什么不让奇数根下面的字符直接$fail=1$,而是让他等于0？
这当然是不对的，跳$fail$的本质过程是判断能不能加入新的位，不能在单个字符周围加入新的字符形成长度为3的新回文串，不代表不能再“0空”位置形成 $aa,bb,cc$这样长度为2的回文串。
本模板题要求以每一位结尾的回文子串个数，设$num[x]$为回文自动机上$x$号点中回文子串个数，当新加入一个点$tot$时，$num[tot]=num[fail[tot]]+1$，即比他的最长回文后缀多含有一个回文子串。
以下是代码,说几个细节问题。
1.如果$i$从$0$开始，$i-len[x]-1$可能出现负数，特判一下。
2.求新点的$fail$时是$getfail(fail[pos],i)$，如果写成了$getfail(pos,i)$，自己会被当成是自己的最长回文后缀(和AC自动机一样不允许！)，$fail$指向自己会导致程序死循环。
3.求新点的$fail$必须在建立新点之前！
否则考虑 要建立奇数根下的点时（abbbc），他们$fail[i]=0$,$getfail(fail[pos],i)$会跳到1(0匹配的话不会再1下建点)，如果1下已经建立它的点，$fail$也会指向他自己导致程序卡死！
时间复杂度$O(n)$，首先建立的节点数是$O(n)$的，其次因为每次执行$while$循环的时候cur的深度会-1，而cur的深度总共增加了n次（for循环中），所以$while$的执行次数也是$O(n)$的
差不多了完结撒花~
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[2000001];
int len[2000001],n,num[2000001],fail[2000001],last,cur,pos,trie[2000001][26],tot=1;
int getfail(int x,int i)
{
while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
return x;
}
int main()
{
scanf("%s",s);
n=strlen(s);
fail[0]=1;len[1]=-1;
for(int i=0;i<=n-1;i++){
if(i>=1)s[i]=(s[i]+last-97)%26+97;
pos=getfail(cur,i);
//找到cur的fail链中能匹配i位的最长回文后缀
if(!trie[pos][s[i]-'a']){
fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a'];
trie[pos][s[i]-'a']=tot;
len[tot]=len[pos]+2;
num[tot]=num[fail[tot]]+1;
}//不存在建立点，存在直接走过去
cur=trie[pos][s[i]-'a'];
last=num[cur];
printf("%d ",last);
}
return 0;
}
```