瞎扯，不做教程。
回文自动机是接受串 \(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;
}