inline int Get_Fail(int x,int i)
{
    while(c[i]!=c[i-len[x]-1]) x=last[x];
    return x;
}
int main()
{
    last[0]=1; len[1]=-1;
    scanf("%s",c+1); n=strlen(c+1); c[0]='~';
    int lastans=0,now=1;
    for(int i=1;i<=n;i++)
    {
        c[i]=(c[i]-97+lastans)%26+97;
        now=Get_Fail(now,i);
        if(!tree[now][c[i]-'a'])
        {
            last[++tot]=tree[Get_Fail(last[now],i)][c[i]-'a'];
            tree[now][c[i]-'a']=tot; f[tot]=f[last[tot]]+1;
            len[tot]=len[now]+2;
        }
        now=tree[now][c[i]-'a'];
        lastans=f[now];
        printf("%d ",lastans);
    }
    printf("\n");
    return 0;
}

关于这段代码，个人认为不能按照类似 $KMP$ 的方式计算复杂度。原因是：

last[++tot]=tree[Get_Fail(last[now],i)][c[i]-'a'];

这段代码虽然调用了 Get_Fail() 函数，但是 now 并没有移动到相应的位置，所以复杂度会退化吗？

下面是我用于测试的代码：cnt 是跳 fail 的次数，n是字符串的长度，然后我对于多个字符串取 cnt/n 的最大值，目前测出来最大是 2.895，看起来确实是线性的，可是怎么证明呢？qwq

#include<bits/stdc++.h>
using namespace std;

const int N=2005+5;

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

char c[N]; int n,cnt=0;
int tree[N][26],len[N],f[N],last[N],tot=1;
inline int Get_fail(int x,int i)
{
	while(c[i]!=c[i-len[x]-1]) x=last[x],cnt++;
	return x;
}
inline int random(int l,int r)
{
	return (long long) rand() * rand() % (r-l+1) + l;
}
inline void Clear()
{
	cnt=0;
	memset(tree,0,sizeof(tree)); 
	memset(len,0,sizeof(len));
	memset(f,0,sizeof(f));
	memset(last,0,sizeof(last));
	tot=1;
}
inline void Make_Data()
{
	n=random(50,100);
	for(int i=1;i<=n;i++) c[i]=random('a','a'+25);
}

int main()
{
	freopen("string.out","w",stdout);
	double Ans=0;
	srand(time(0));
	int T=random(10000,20000);
	while(T--)
	{
		Clear(); 
		Make_Data();
		last[0]=1; len[1]=-1; c[0]='~';
		int now=1;
		for(int i=1;i<=n;i++)
		{
			int x=(c[i]-'a');
			now=Get_fail(now,i);
			if(!tree[now][x])
			{
				last[++tot]=tree[Get_fail(last[now],i)][x];
				tree[now][x]=tot; f[tot]=f[last[tot]]+1;
				len[tot]=len[now]+2;
			}
			now=tree[now][x];
		}
		Ans=max(Ans,(double)cnt/n);
	}
	printf("maxx=%.3lf\n",Ans);
	return 0;
}