代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2000010;
int tax[N],x[N],y[N],n,m,num,sa[N],rk[N],h[N];
char S[N];
void suffix_sort()  {
	m=256;
	for(int i=1;i<=n;++i)++tax[x[i]=S[i]];
	for(int i=2;i<=m;++i)tax[i]+=tax[i-1];
	for(int i=1;i<=n;++i)sa[tax[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1) {
		num=0;
		for(int i=n-k+1;i<=n;++i)y[++num]=i;
		for(int i=1;i<=n;++i)if(sa[i]>k)y[++num]=sa[i]-k;
		for(int i=1;i<=m;++i)tax[i]=0;
		for(int i=1;i<=n;++i)++tax[x[i]];
		for(int i=2;i<=m;++i)tax[i]+=tax[i-1];
		for(int i=n;i>=1;--i)sa[tax[x[y[i]]]--]=y[i],y[i]=0;
		num=1;
		swap(x,y);x[sa[1]]=1;
		for(int i=2;i<=n;++i)
		x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(num==n)break;
		m=num;
	}
	for(int i=1;i<=n;++i)rk[sa[i]]=i;
	for(int i=1,j;i<=n;++i) {
		j=h[rk[i-1]]-1;
		if(j<0)j=0;
		while(S[i+j]==S[sa[rk[i]-1]+j])++j;
		h[rk[i]]=j;
	}
}
int main() {
	scanf("%s",S+1);
	n=strlen(S+1);
	suffix_sort();
	for(int i=1;i<=n;++i)printf("%d ",sa[i]);puts("");
	for(int i=2;i<=n;++i)printf("%d ",h[i]);
	return 0;
}

评测结果