回文自动机（PAM）

瞎扯，不做教程。

回文自动机是接受串 \(s\) 所有本质不同回文子串的类自动机结构。

考察该类自动机结构的转移边上字符的含义，因为回文串是回文的，所以从 \(s\) 转移到 \(t\) 应该在 \(s\) 所代表的字符串两边均加上转移边上的字符 \(c\)。

这样就会有一个问题：考虑每次走转移边字符串长度都增加 \(2\)，那么奇回文串怎么办？

为了解决这个问题，我们建立奇偶两根，偶根长度为 \(0\)，奇根长度为 \(-1\)。这样长度为奇数的回文串都接在奇根下面。

那么 fail 咋整呢？为了方便，我们直接把偶根的 fail 设为奇根，体会一下代码就会发现妙处。接下来我们要插入字符串中的每一个字符，首先记下插入 \(s[1,i-1]\) 后所在节点 \(lst\)（即 \(s[1,i-1]\) 的最长回文后缀），然后考虑从 \(lst\) 开始一直跳 fail，直到 \(lst\) 所对应字符串在原串中的前一个位置和 \(s_i\) 相等，如果 \(lst\) 的 \(s_i\) 出边没有节点，那么就新建一个，否则无事发生。

考虑新建节点的 fail，就是从 \(lst\) 的 fail 开始跳 fail，直到前一个位置和 \(s_i\) 相等即可。

容易证明时间复杂度 \(O(n)\)。

# include <bits/stdc++.h>

const int N=500010,INF=0x3f3f3f3f;

struct pam{
	int ch[26],len,fail;
}tr[N];

int num[N];

char s[N];
int n; 
int cnt,last;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline int NewNode(int l){
	tr[++cnt].len=l;
	return cnt;
}
inline void init(void){
	cnt=-1,NewNode(0),NewNode(-1),s[0]='#',tr[0].fail=1;
	return;
}
inline int getfail(int x,int clen){
	while(s[clen-1-tr[x].len]!=s[clen]) x=tr[x].fail;
	return x;
}
inline int ins(int x){
	int cur=getfail(last,x),p=-1;
	if(!tr[cur].ch[s[x]-'a']){
		p=NewNode(tr[cur].len+2),tr[p].fail=tr[getfail(tr[cur].fail,x)].ch[s[x]-'a'],tr[cur].ch[s[x]-'a']=p;
		num[p]=num[tr[p].fail]+1;
	}
	last=tr[cur].ch[s[x]-'a'];
	return num[last];
}

int main(void){
	scanf("%s",s+1),n=strlen(s+1);
	init();
	int lst=0;
	for(int i=1;i<=n;++i){
		if(i>=1) s[i]=(s[i]-'a'+lst)%26+'a';
		printf("%d ",lst=ins(i));
	}
	
	return 0;
}