代码

#include <cstdio>
#include <cstring>
//#include <iostream>
#define oo 2139062143
#define fo(i,x,y) for (int i=(x);i<=(y);++i)
#define fd(i,x,y) for (int i=(x);i>=(y);--i)
using namespace std;
const int N=100100,L=100100,C=27;
char s[L],t[L];
int n,m,l,ct;
int sa[N],rnk[N],w[N],se[N];
void gt_sa()
{
	fo(i,0,ct) w[i]=0;
	fo(i,1,n) ++w[rnk[i]];
	fo(i,1,ct) w[i]+=w[i-1];
	fd(i,n,1) sa[w[rnk[se[i]]]--]=se[i];
}
int same(int x,int y,int len)
{
	return(se[x]==se[y]&&se[x+len]==se[y+len]);
}
int h[N],he[N];
int max(int x,int y)
{
	return(x>y)?x:y;
}
void get_sa()
{
	ct=C;rnk[n+1]=-1;
	fo(i,1,n) se[i]=i,rnk[i]=s[i]-'a'+1;
	gt_sa();
	for(int len=1;len<=n;len<<=1)
	{
		int tct=0;
		fo(i,n-len+1,n) se[++tct]=i;
		fo(i,1,n) if(sa[i]>len) se[++tct]=sa[i]-len;
		gt_sa();
//		swap(rnk,se);
		fo(i,1,n) se[i]=rnk[i];
		rnk[sa[1]]=ct=1;
		fo(i,2,n)
		if(!same(sa[i-1],sa[i],len)) 
			rnk[sa[i]]=++ct;
		else rnk[sa[i]]=ct;
	}
	fo(i,1,n)
	{
		h[i]=max(h[i-1]-1,0);	
		while(s[i+h[i]]==s[sa[rnk[i]-1]+h[i]]) ++h[i];
	}
	fo(i,1,n) he[i]=h[sa[i]];
}
int main()
{
//	freopen("D:/LiuYuanHao/a.in","r",stdin);
	scanf("%s\n",s+1);n=strlen(s+1);
	get_sa();
	fo(i,1,n) printf("%d ",sa[i]);
	printf("\n");
	fo(i,2,n) printf("%d ",he[i]);
	return 0;
}

评测结果