一眼恶心kmp。 例题和题解详见：https://blog.csdn.net/tenkuo/article/details/152000561

本题题解注释代码：

#include<bits/stdc++.h> 
using namespace std;
 
typedef long long LL;
const int N = 5e5 + 10; 
char s[N];    
LL z[N];          // z: s 的 Z 函数数组
int len;
 
// 计算文本串 s 的 Z 函数
// z[i] 表示 s[i..lenb]与 s[1..lenb] 的最长公共前缀长度（LCP） 
void get_z() {
	memset(z, 0, sizeof(z)); 
    z[1] = len;  // 特殊情况：s[1..lenb]与自身的 LCP 就是整个字符串长度
    
    // 初始化最右匹配区间 [l, r]
    // 这区间就是 s[l..r] = s[1..r - l + 1]
    // l、r: 当前已知最右匹配区间的左端点和右端点
    for (int i = 2, l = 0, r = 0; i <= len; i ++) {
    	// i 从 2 开始，代表后缀开始的位置，l = r = 0，一开始并没有区间 
        // 如果 i 在当前最右匹配区间 [l, r] 内
        if (i <= r) {
            z[i] = min(z[i - l + 1], 1ll * (r - i + 1));
            // 根据定义 1 到 r - l + 1 和 l 到 r 是相等的
			// 所以 i - l + 1 到 r - l + 1 和 i 到 r 是相等的
			// 因此以 i - l + 1 为标准，最大 LCP 最多就可以取 r - i + 1
			// 但是如果这个 r - i + 1 比 z[i - l + 1] 还要大的话，那当然取不了
			// 反之 r - i + 1 比 z[i - l + 1] 小，那也不能取大的
			// 因为只有 i - l + 1 到 r - l + 1 是相等的 
        }
        
        // 从 z[i] 开始尝试扩展匹配
        // 检查 s[1 + z[i]] 和 s[i + z[i]] 是否相等
        while (1 + z[i] <= len && i + z[i] <= len && s[1 + z[i]] == s[i + z[i]]) {
            z[i] ++;     // 匹配成功，LCP 长度 + 1
        }
        
        // 如果匹配后右边界超过当前最右匹配区间，则更新区间
        if (i + z[i] - 1 > r) {
            l = i;                // 新区间的左端点
            r = i + z[i] - 1;     // 新区间的右端点
        }
    }
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> (s + 1);
    len = strlen(s + 1);
    
    get_z();

    for (int i = 1; i <= len; i ++) {
        cout << z[i] << " ";
    }
    cout << "\n";
    
    return 0;
}

SA秒了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=5e5+10;
int n,m,p,sa[mxn],rk[mxn],oldrk[mxn],height[mxn],cnt[mxn],id[mxn],st[mxn][25],lg2[mxn];
int get(int l,int r){
	if(l==r)return n-sa[l]+1;
	if(l>r)swap(l,r);
	r--;
	int d=lg2[r-l+1];
	return min(st[l][d],st[r-(1<<d)+1][d]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	n=s.size();
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	s=" "+s;
	m=255;
	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;p<n;w<<=1,m=p){
		int cur=0;
		for(int i=n-w+1;i<=n;i++)id[++cur]=i;
		for(int i=1;i<=n;i++)if(sa[i]>w)id[++cur]=sa[i]-w;
		for(int i=1;i<=m;i++)cnt[i]=0;
		for(int i=1;i<=n;i++)cnt[rk[i]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		memcpy(oldrk,rk,sizeof(rk));
		p=0;
		for(int i=1;i<=n;i++){
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
	}
	for(int i=1,k=0;i<=n;i++){
		if(rk[i]==n)continue;
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]+1]+k])k++;
		height[rk[i]]=k;
		st[rk[i]][0]=k;
	} 
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<n;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<get(rk[i],rk[1])<<' ';
	}
	return 0;
}

代码背了但是没读懂。何为 exkmp？

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
char st[N];int z[N];
signed main()
{
	scanf("%s",st+1);int n=strlen(st+1);
	z[1]=n;
	for(int i=2,l=1,r=1;i<=n;i++)
	{
		if(i<=r&&z[i-l+1]<r-i+1)z[i]=z[i-l+1];
		else 
		{
			z[i]=max(0,r-i+1);
			while(i+z[i]<=n&&st[z[i]+1]==st[i+z[i]])z[i]++;
		}
		if(i+z[i]-1>r)l=i,r=i+z[i]-1;
	}
	for(int i=1;i<=n;i++)cout<<z[i]<<' ';cout<<'\n';
	return 0;
}