回文自动机（PAM）

回文自动机，也称回文树，是用来解决一些manacher算法不容易解决的回文串的问题，比如求解字符串s中以第i个字符结尾的回文串的个数。当然它还可以用于求解本质不同的回文子串的数目，所有的回文子串的数目，其复杂度也都是O（n）的，其中n是字符串的长度。

我们下面就以求解一个串中本质不同的回文子串为例讲解回文自动机。当然这个问题也可以用manacher+哈希来求解，方法我在之前的博客中有过介绍，感兴趣的小伙伴可以看一下，这样做的复杂度是O(n)的，manacher的思想就是利用回文子串的对称性质来进行优化，而在利用对称性质所省略的那些回文串都是之前出现过的字符串，恰好不会包含本质不同的回文子串这种情况，所以我们只需要在manacher暴力扩展的时候统计一下本质不同的回文子串即可。

而回文自动机本质上就是两棵树，一棵树上挂着长度为奇数的回文串，另一棵树上挂着长度为偶数的回文串，0代表偶数长度的根，1代表奇数长度的根。我们利用一个回文串去掉两头之后还是一个回文串的性质把所有的回文串都存储在树上。树上的每个节点都代表着一个字符串。

先来说一下数组的含义

对于第i个回文串

tree[i][c]代表第i个回文串的两边添加一个字符c对应的回文串的编号

len[i]代表第i个回文串的长度

fail[i]代表第i个回文串不包含自身的最长回文后缀对应的编号

num[]代表以当前字符结尾的回文串的个数

其中默认len[0]=0,len[1]=-1。

len[0]=0很好理解，那么len[1]=-1是什么意思呢？因为我们每次都是在一个回文串两边分别加上一个字符然后再判断这个串是否还是回文串，所以长度每次是+2，当一个空奇数长度的回文串添加两个字符后恰好长度为1，这就相当于一个字符本身，所以就初始化len[1]=-1.无论是奇数长度的回文串还是偶数长度的回文串，每次扩展长度都会+2

那我们怎么把这些回文字符串存到树上呢？类似于字典树，每次向树上加一个字符，也就是说我们向s[1~i-1]的回文树上加第i个字符，我们现在来考虑怎么更新这些数组，由于所有新产生的回文子串都是新最长回文子串的回文后缀，且长度应比最长的小，我们可以把他们“翻转”一下，就可以发现他们一定在s[0~i-1]的回文树里，所以插入一个新点，最多只会建立“最长新回文后缀”这么一个节点，保证了回文自动机的点数是O(n)的。

如果以当前字符结尾的最长回文子串已经存储在树中那么我们就直接走过去就行，而如果没有存储在树上，我们需要新开一个节点存储当前最长回文子串，那么当前回文子串的fail指针怎么更新呢？我们利用前一个字符形成的fail指针进行更新而不能利用前一个字符形成的最大回文子串来进行更新，大家可以考虑下这是为什么？因为我前面已经说过了fail指针所指向的最长回文后缀是不等于当前子串的，而如果利用前一个字符形成的最大回文子串来进行更新最后是有可能使得fail指针指向的字符串就是自身，那么在遍历的时候就会造成死循环，所以这一点需要切记，然后就可以更新tree[][s[i]]，这个就直接等于新开的编号即可，注意一定要先对新开节点的fail指针进行更新后对tree进行更新，否则会出现死循环，原因就出现在如果当前节点是一个连在奇根上的单个字符，那么先对tree进行更新的话，那么更新fail的时候就会陷入死循环，这个模拟一下就知道了。len的话就直接等于找到的扩展前的回文子串长度+2即可，num就等于num[fail]+1，因为根据fail的定义也知道fail是不包含自身的最长回文后缀，那么加上自身这个回文子串就是所有的以当前字符结尾的回文串。

最后新开节点的个数就是我们本质不同的回文子串的个数（也就是除了节点0和1之外的所有节点）

num[]数组元素和就是所有回文子串的个数

下面给出一个例题并给出代码：

题目链接：【模板】回文自动机（PAM） - 洛谷

 样例输入：

debber

样例输出：

1 1 1 2 1 1

代码：
 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=5e5+10;
int fail[N],tree[N][30],idx=1;
int len[N];//len[i]表示编号为i的回文串的长度
int num[N];//num[]表示以第当前位置的字符结尾的回文串的个数 
char s[N];
int getfail(int x,int i)
{
	while(s[i-len[x]-1]!=s[i]) x=fail[x];//当跳到奇根上时一定有s[i]=s[i] 
	return x;
}
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	fail[0]=1;//偶根的fail指针指向奇根 
	len[1]=-1;//奇根的长度默认为-1 
	int ans=0,id=0;
	for(int i=1;i<=n;i++)
	{
		if(i!=1) s[i]=(s[i]-97+ans)%26+97;
		id=getfail(id,i);
		if(!tree[id][s[i]-'a'])
		{
			fail[++idx]=tree[getfail(fail[id],i)][s[i]-'a'];
			tree[id][s[i]-'a']=idx;
			len[idx]=len[id]+2;
			num[idx]=num[fail[idx]]+1;
		}
		id=tree[id][s[i]-'a'];
		ans=num[id];
		printf("%d ",ans);
	}
	return 0;
}