代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200005
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, s[N], s1[N], sa[N], cnt[N], p[N], rk[N], idx[N];//type S:0 L:1
bool t[N];
#define pushl(x) sa[idx[s[x]]++]=x
#define pushs(x) sa[idx[s[x]]--]=x
void inducedsort(int *s, bool *t, int *sa, int *cnt, int n, int m, int *v, int top)
{
	std::fill(sa+1, sa+n+1, 0);
	memcpy(idx, cnt, sizeof(int)*(m+1));
	for(int i=top; i; --i) pushs(v[i]);
	for(int i=1; i<=m; ++i) idx[i]=cnt[i-1]+1;
	for(int i=1; i<=n; ++i)
	{
		int x=sa[i]-1;
		if(x&&t[x]) pushl(x);
	}
	memcpy(idx, cnt, sizeof(int)*(m+1));
	for(int i=n; i; --i)
	{
		int x=sa[i]-1;
		if(x&&!t[x]) pushs(x);
	}
}
void SAIS(int *s, bool *t, int *p, int *cnt, int n, int m)
{
	int top=0, *s1=s+n+1;
	t[n]=0;
	for(int i=1; i<=n; ++i) ++cnt[s[i]];
	for(int i=1; i<=m; ++i) cnt[i]+=cnt[i-1];
	for(int i=n-1; i; --i) t[i]=(s[i]>s[i+1]||(s[i]==s[i+1]&&t[i+1]));
	for(int i=2; i<=n; ++i) rk[i]=((t[i-1]&&!t[i])?(p[++top]=i, top):0);
	inducedsort(s, t, sa, cnt, n, m, p, top);
	int nm=0;
	for(int i=1, x=0, y=0; i<=n; ++i) if(x=rk[sa[i]])
	{
		if(!m||p[x+1]-p[x]!=p[y+1]-p[y]) ++nm;
		else
		{
			if(memcmp(s+p[x], s+p[y], sizeof(int)*(p[x+1]-p[x]+1))) ++nm;
		}
		y=x;
		s1[x]=nm;
	}
	if(nm<top) SAIS(s1, t+n+1, p+n+1, cnt+m+1, top, nm);
	else for(int i=1; i<=top; ++i) sa[s1[i]]=i;
	for(int i=1; i<=top; ++i) s1[i]=p[sa[i]];
	inducedsort(s, t, sa, cnt, n, m, s1, top);
}
char rs[N];
int h[N];
inline void gheight(void)
{
	for(int i=1; i<=n; ++i) rk[sa[i]]=i;
	for(int i=1, k=0; i<=n; ++i) if(rk[i]<n)
	{
		int j=sa[rk[i]+1];
		k=std::max(0, k-1);
		while(rs[i+k]==rs[j+k]) ++k;
		h[rk[i]]=k;
	}
}
int main()
{
	char c=gc();
	while(c!='\n'&&c!='\r'&&c!=EOF) rs[++n]=c, c=gc();
	for(int i=1; i<=n; ++i) s[i]=rs[i];
	s[++n]=1;
	SAIS(s, t, p, cnt, n, 'z'+2);
	for(int i=1; i<n; ++i) sa[i]=sa[i+1];
	sa[n]=0;
	--n;
	for(int i=1; i<=n; ++i) putint(sa[i], ' ');
	pc('\n');
	gheight();
	for(int i=1; i<n; ++i) putint(h[i], ' ');
	pc('\n');
	flush();
	return 0;
}

评测结果