代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
int n, *rk, *ork, rid[N], pool[2][N], sa[N], cnt[N], id[N], h[N], tp;
char s[N];
inline int eq(int x, int y, int len) { return ork[x]==ork[y]&&ork[x+len]==ork[y+len]; }
inline void SA(void)
{
	rk=pool[0], ork=pool[1];
	for(int i=1; i<=n; ++i) ++cnt[rk[i]=s[i]-'a'+1];
	for(int i=1; i<=26; ++i) cnt[i]+=cnt[i-1];
	for(int i=1; i<=n; ++i) sa[cnt[rk[i]]--]=i;
	for(int len=1, lim=0; lim!=n; len<<=1)
	{
		if(!lim) lim=26;
		tp=0;
		for(int i=n-len+1; i<=n; ++i) id[++tp]=i;
		for(int i=1; i<=n; ++i) if(sa[i]>len) id[++tp]=sa[i]-len;
		
		std::fill(cnt+1, cnt+lim+1, 0);
		for(int i=1; i<=n; ++i) ++cnt[rk[i]];
		for(int i=1; i<=lim; ++i) cnt[i]+=cnt[i-1];
		for(int i=1; i<=n; ++i) rid[i]=rk[id[i]];
		for(int i=n; i; --i) sa[cnt[rid[i]]--]=id[i];
		
		std::swap(rk, ork);
		lim=0;
		for(int i=1; i<=n; ++i)
		{
			if(i==1||(!eq(sa[i-1], sa[i], len))) rk[sa[i]]=++lim;
			else rk[sa[i]]=lim;
		}
	}
}
inline void gheight(void)
{
	for(int i=1, k=0; i<=n; ++i)
	{
		if(rk[i]==1) continue;
		if(k) --k;
		int j=sa[rk[i]-1];
		while(s[i+k]==s[j+k]) ++k;
		h[rk[i]]=k;
	}
}
int main()
{
	scanf("%s", s+1);
	n=strlen(s+1);
	SA();
	gheight();
	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;
}

评测结果