代码

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(register int i=(j),LIM=(k);i>=LIM;i--)
#define maxn 100005
#define Ct const
using namespace std;

namespace SA{
	int sa[maxn],h[maxn],rk[maxn],c[maxn],l[maxn],p[maxn],s[maxn<<1],t[maxn<<1];
	#define pushS(x) sa[l[s[x]]--]=x
	#define pushL(x) sa[l[s[x]]++]=x 
	#define _Sort(v) fill(sa,sa+n,-1),fill(c,c+m,0);   							 \
	rep(i,0,n-1) c[s[i]]++;rep(i,1,m-1) c[i]+=c[i-1]; 						 	 \
	rep(i,0,m-1) l[i]=c[i]-1;per(i,n1-1,0) pushS(v[i]);							 \
	rep(i,0,m-1) l[i]=c[i-1];rep(i,0,n-1) if(sa[i]>0&&t[sa[i]-1]) pushL(sa[i]-1);\
	rep(i,0,m-1) l[i]=c[i]-1;per(i,n-1,0) if(sa[i]>0&&!t[sa[i]-1])pushS(sa[i]-1);
	void sais(int n,int m,int *s,int *t,int *p){
		int n1 = t[n-1] = 0 , ch = rk[0] = -1 , *s1 = s+n;
		per(i,n-2,0) t[i]=s[i]^s[i+1]?s[i]>s[i+1]:t[i+1];
		rep(i,1,n-1) rk[i]=t[i-1]&&!t[i]?p[n1]=i,n1++:-1;
		_Sort(p);
		for(int i=0,x,y;i<n;i++) if(~(x=rk[sa[i]])){
			if(ch<0||(p[x+1]-p[x])^(p[y+1]-p[y])) ch++;
			else for(int j=p[x],k=p[y];j<=p[x+1];j++,k++) 
				if((s[j]<<1|t[j])^(s[k]<<1|t[k])){ ch++;break; }
			s1[y=x]=ch;}
		if(ch+1<n1) sais(n1,ch+1,s1,t+n,p+n1);
		else rep(i,0,n1-1) sa[s1[i]]=i;
		rep(i,0,n1-1) s1[i]=p[sa[i]];
		_Sort(s1);
	}
	template<class T>void SA(int n,Ct T &S){
		rep(i,0,n-1) s[i]=S[i];s[n++]=0;
		sais(n,200,s,t,p);
		rep(i,0,n-1) rk[sa[i]]=i;
		for(int i=0,k=0;i<n-1;h[rk[i++]]=k)
			for(k&&k--;s[i+k]==s[sa[rk[i]-1]+k];k++);
	}
}	
using SA::sa;
using SA::h;
using SA::rk;

char output_buffer[maxn * 20], *output_ptr = output_buffer;
void print(int v, char step = ' ')
{
	if (v)
	{
		static int str[20];
		int len = 0;
		for (; v; v /= 10) str[len++] = v % 10;
		while (len--) *output_ptr++ = str[len] + '0';
	}
	else *output_ptr++ = '0';
	*output_ptr++ = step;
}
void flush()
{
	fwrite(output_buffer, 1, output_ptr - output_buffer, stdout);
}

int main(){
	static char s[maxn];
	scanf("%s",s);
	int n = strlen(s);
	SA::SA(n,s);
	rep(i,1,n) print(sa[i]+1," \n"[i==n]);
	rep(i,2,n) print(h[i]," \n"[i==n]);
	flush();
}

评测结果