注意事项

初始有两个根01，分别对应奇偶，长度为0/-1,0的fail是1

如果跳到了1号点，那么新建的点的fail是0

种数=点数-1，某个串结尾的回文子串个数=fail链长度

扩展要考虑匹配以及边界

code

洛谷5496

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
//#define file
using namespace std;

int tr[500011][26],fa[500011],sum[500011],Len[500011],n,i,j,k,l,ans,len;
char st[500001],ch;

int main()
{
    #ifdef file
    freopen("luogu5496.in","r",stdin);
    freopen("luogu5496.out","w",stdout);
    #endif

    len=1;l=0;
    fa[0]=fa[1]=1;
    Len[0]=0,Len[1]=-1;

    ch=getchar();
    while (ch>='a' && ch<='z')
    {
        ch=(ch-97+ans)%26+97;

        st[++n]=ch;j=l;
        while (n-Len[l]-1<1 || st[n-Len[l]-1]!=ch) l=fa[l];
        if (!tr[l][ch-'a'])
        {
            tr[l][ch-'a']=++len;Len[len]=Len[l]+2;
            j=fa[l];
            while (n-Len[j]-1<1 || st[n-Len[j]-1]!=ch) j=fa[j];

            fa[len]=(j==l)?0:tr[j][ch-'a'];sum[len]=sum[fa[len]]+1;
        }
        l=tr[l][ch-'a'];

        ans=sum[l],printf("%d ",ans);
        ch=getchar();
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}