代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
char S[N];
int n,m,num,id[N],sa[N],cnt[N],h[N],rk[N];
void suffix_sort() {
	m=300;
	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>=1;--i)sa[cnt[rk[i]]--]=i;
	for(int w=1;w<n;w<<=1) {
		num = 0;
		for(int i = n - w + 1; i <= n; i++) id[++num] = i;
		for(int i = 1; i <= n; i++) if(sa[i] > w) id[++num] = 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 >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i], id[i] = 0;
		swap(id, rk), rk[sa[1]] = num = 1;
		for(int i = 2; i <= n; i++)
			rk[sa[i]] = (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + w] == id[sa[i - 1] + w])? num : ++num;
		m=num;
	}
	for(int i=1,j=0;i<=n;++i) {
		if(j)--j;
		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;
}

评测结果