总

复杂度证明比起 SAM 较简单（虽然我还是没想出来），用学长魏忠浩的一句话就行了：

考虑当前点 fail 指针指向的节点的长度，跳一次至少减，插入至多加常数

难点在于代码细节，想不去讨论初始情况的一坨就必须注意细节。

CODE

  • fail 必须在 ch 之前算，而且偶数根必须是 0，这样单字母的节点才可以老老实实把 fail 指向 0，也才不会出现一个点莫名其妙就把 fail 指针指自己。

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;++i)
#define frd(i,j,k) for(int i=j;i>=k;--i)
#define pc(x) putchar(x)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;using ll = long long;
namespace ugi{
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
}
using ugi::in;
const int maxn=(int)(5e5+12);
int n,nl[maxn];
char str[maxn];
int ch[26][maxn],fail[maxn],len[maxn],cnt,lt=1;
void init(void)
{
    cnt=1;len[0]=0;len[1]=-1;fail[0]=1;
}
int getpt(int p,int x)
{
    while(str[p]!=str[p-len[x]-1])
    {
        x=fail[x];
    }
    return x;
}
int main()
{
    // fio();
    scanf("%s",str+1);n=strlen(str+1);
    int la=0,c;
    init();
    fru(i,1,n)
    {
        str[i]=(str[i]-97+la)%26+97;c=str[i]-'a';
        lt=getpt(i,lt);
        if(!ch[c][lt])
        {
            len[++cnt]=len[lt]+2;
            fail[cnt]=ch[c][getpt(i,fail[lt])];
            ch[c][lt]=cnt;
            nl[cnt]=nl[fail[cnt]]+1;
        }
        lt=ch[c][lt];
        printf("%d ",la=nl[lt]);
        // cerr<<i<<' '<<str[i]<<' '<<lt<<' '<<fail[lt]<<' '<<len[lt]<<endl;
    }
    return 0;
}