代码

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

#define Uni All Right
#define REP(i,a,b) for(int i=(a),i##_end_=(b);i<i##_end_;++i)
#define DREP(i,a,b) for(int i=(a),i##_end_=(b);i>i##_end_;--i)
#define LREP(i,a) for(int i=Head[a];i;i=Next[i])
#define LL long long

static const int M=100004;
int n,k,Cnt[M];
int SA[M],Ht[M<<1],Rk[M<<1];
char S[M];
void Init(){
	int *A=Rk,*B=Ht;
	REP(i,1,n+1)++Cnt[A[i]=(S[i]-'a'+1)];
	REP(i,1,233)Cnt[i]+=Cnt[i-1];
	REP(i,1,n+1)SA[Cnt[A[i]]--]=i;
	
	for(int v=1;v<=n;v<<=1){
		int m=0;
		REP(i,n-v+1,n+1)B[++m]=i;
		REP(i,1,n+1){
			if(SA[i]>v)B[++m]=SA[i]-v;
			Cnt[A[SA[i]]]=i;
		}
		DREP(i,n,0)SA[Cnt[A[B[i]]]--]=B[i];
		
		B[SA[1]]=m=1;
		REP(i,2,n+1)B[SA[i]]=B[SA[i-1]]+(A[SA[i]]!=A[SA[i-1]] || A[SA[i]+v]!=A[SA[i-1]+v]);
		swap(A,B);
		if(A[SA[n]]==n)break;
	}
	
	REP(i,1,n+1)Rk[SA[i]]=i;
	int h=0,j;
	REP(i,1,n+1)if((j=Rk[i])>1){
		h?--h:0;
		j=SA[j-1];
		while(i+h<=n && j+h<=n && S[i+h]==S[j+h])++h;
		Ht[Rk[i]]=h;
	}
}
int main(){
	scanf("%s",S+1);
	n=strlen(S+1);
	Init();
	REP(i,1,n+1)printf("%d%c",SA[i]," \n"[i==n]);
	REP(i,2,n+1)printf("%d%c",Ht[i]," \n"[i==n]);
	
	return 0;
}

评测结果