代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
namespace iobuff{
	const int LEN=1000000;
	char in[LEN+5], out[LEN+5];
	char *pin=in, *pout=out, *ed=in, *eout=out+LEN;
	inline char gc(void)
	{
		return pin==ed&&(ed=(pin=in)+fread(in, 1, LEN, stdin), ed==in)?EOF:*pin++;
	}
	inline void pc(char c)
	{
		pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out);
		(*pout++)=c;
	}
	inline void flush()
	{ fwrite(out, 1, pout-out, stdout), pout=out; }
	template<typename T> inline void scan(T &x)
	{
		static int f;
		static char c;
		c=gc(), f=1, x=0;
		while(c<'0'||c>'9') f=(c=='-'?-1:1), c=gc();
		while(c>='0'&&c<='9') x=10*x+c-'0', c=gc();
		x*=f;
	}
	template<typename T> inline void putint(T x, char div)
	{
		static char s[15];
		static int top;
		top=0;
		x<0?pc('-'), x=-x:0;
		while(x) s[top++]=x%10, x/=10;
		!top?pc('0'), 0:0;
		while(top--) pc(s[top]+'0');
		pc(div);
	}
}
using namespace iobuff;
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) putint(sa[i], ' ');
	pc('\n');
	for(int i=2; i<=n; ++i) putint(h[i], ' ');
	flush();
	return 0;
}

评测结果