代码

#include<bits/stdc++.h>
const int N=1e5+5;
char s[N];
int sa[N],h[N],u[N],v[N],c[N];
int main(){
	int i,j,k=0,n,m=131,*rk=u,*tp=v,*z;
	gets(s+1),n=strlen(s+1);
	for(i=1;i<=n;++i)++c[rk[i]=s[i]];
	for(i=2;i<=m;++i)c[i]+=c[i-1];
	for(i=n;i;--i)sa[c[rk[i]]--]=i;
	for(i=1;i<=n&&k<n;m=k,i<<=1){
		for(j=n-i+1,k=0;j<=n;++j)tp[++k]=j;
		for(j=1;j<=n;++j)if(sa[j]>i)tp[++k]=sa[j]-i;
		memset(c+1,0,sizeof(int[m]));
		for(j=1;j<=n;++j)++c[rk[j]];
		for(j=2;j<=m;++j)c[j]+=c[j-1];
		for(j=n;j;--j)sa[c[rk[tp[j]]]--]=tp[j];
		z=rk,rk=tp,tp=z,rk[sa[1]]=k=1;
		for(j=2;j<=n;++j)rk[sa[j]]=tp[sa[j]]==tp[sa[j-1]]&&tp[sa[j]+i]==tp[sa[j-1]+i]?k:++k;
	}
	for(i=1;i<=n;++i)printf("%d ",sa[i]);
	for(i=1,k=0;i<=n;++i){
		if(rk[i]==1)continue;
		if(k)--k;
		for(j=sa[rk[i]-1];s[i+k]==s[j+k];++k);
		h[rk[i]]=k;
	}
	for(puts(""),i=2;i<=n;++i)printf("%d ",h[i]);
	return 0;
}

评测结果