代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,sa[N],rk[N],m=122,c[N],y[N];
char s[N];
inline bool cmp(int a,int b,int k){return y[a]==y[b]&&y[a+k]==y[b+k];}

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;

inline void getsa(){
	for(int i=1;i<=n;++i) rk[i]=s[i],c[rk[i]]++;
	for(int i=2;i<=m;++i) c[i]+=c[i-1];
	for(int i=n;i>=1;--i) sa[c[rk[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
		int num=0;
		for(int i=n-k+1;i<=n;++i) y[++num]=i;
		for(int i=1;i<=n;++i) (sa[i]>k)&&(y[++num]=sa[i]-k);
		for(int i=1;i<=m;++i) c[i]=0;
		for(int i=1;i<=n;++i) c[rk[i]]++;
		for(int i=2;i<=m;++i) c[i]+=c[i-1];
		for(int i=n;i>=1;--i) sa[c[rk[y[i]]]--]=y[i],y[i]=rk[i];
		rk[sa[1]]=num=1;
		for(int i=2;i<=n;++i)
			rk[sa[i]]=cmp(sa[i],sa[i-1],k)?num:++num;
		m=num;
		if(num==n) break;
	}
}
int height[N],h[N];
inline void getheight(){
	int k=0;
	for(int i=1;i<=n;++i){
		if(rk[i]==1) continue;
		if(k) --k;
		int j=sa[rk[i]-1];
		while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k]) ++k;
		height[rk[i]]=k;  
	}
	for(int i=2;i<=n;++i) putint(height[i],' ');
}
int main(){
	scanf("%s",s+1);n=strlen(s+1);
	getsa();
	for(int i=1;i<=n;++i) putint(sa[i],' ');pc('\n');
	getheight();pc('\n');
	flush();
	return 0;
}

评测结果