PAM模板

#include <bits/stdc++.h>
using namespace std;
const int M=5e5+5;

char s[M];
int len[M],num[M],fail[M],ch[M][26],tot=1;

int get_fail(int x,int i) {
    while(i-len[x]-1<=0||s[i-len[x]-1]!=s[i])x=fail[x];
    return x;
}

void PAM(char *s) {
    int n=strlen(s+1);
    int last=0,now=0;
    fail[0]=1,len[1]=-1;
    for(int i=1;i<=n;i++) {
        if(i>1)s[i]=(s[i]+last-97)%26+97;
        int pos=get_fail(now,i);
        if(!ch[pos][s[i]-'a']) {
            fail[++tot]=ch[get_fail(fail[pos],i)][s[i]-'a'];
            //需要先建立点，不然不知道往哪里走
            ch[pos][s[i]-'a']=tot;
            len[tot]=len[pos]+2;
            num[tot]=num[fail[tot]]+1;
            //注意这里是看的fail指针的地方
        }
        now=ch[pos][s[i]-'a'];
        last=num[now];
        cout<<last<<' ';
    }
}

int main() {
    scanf("%s",s+1);
    PAM(s);
    return 0;
}