Manacher&PAM
题单介绍
```cpp
#include<bits/stdc++.h>
#define maxn 2000010
using namespace std;
char s[maxn];
int len[maxn],n,num[maxn],fail[maxn],last,cur,pos,trie[maxn][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);
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;
}
```