代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+1e3+7;

int sa[N],wa[N],wb[N],wv[N],tong[N],rk[N],height[N]; 

char s[N];

int n;

bool cmp(int *r,int a,int b,int l)
{
	return r[a]==r[b]&&r[a+l]==r[b+l];
}

void da(char *r,int *sa,int n,int m)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for(i=0;i<n;i++)
		tong[x[i]=r[i]]++;
	for(i=1;i<m;i++)
		tong[i]+=tong[i-1];
	for(i=n-1;i>=0;i--)
		sa[--tong[x[i]]]=i;
	for(j=1,p=0;j<n;j<<=1,m=p)
	{
		for(i=n-j,p=0;i<n;i++)
			y[p++]=i;
		for(i=0;i<n;i++)
			if(sa[i]>=j)
				y[p++]=sa[i]-j;
		for(i=0;i<m;i++)
			tong[i]=0;
		for(i=0;i<n;i++)
			tong[wv[i]=x[y[i]]]++;
		for(i=1;i<m;i++)
			tong[i]+=tong[i-1];
		for(i=n-1;i>=0;i--)
			sa[--tong[wv[i]]]=y[i];
		for(t=x,x=y,y=t,x[sa[0]]=0,i=1,p=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}

void calheight(char *r,int *sa,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++)
		rk[sa[i]]=i;
	for(i=0;i<n;height[rk[i++]]=k)
		for(k?k--:0,j=sa[rk[i]-1];r[i+k]==r[j+k];k++);
}

int main()
{
	scanf("%s",s);
	n=strlen(s);
	da(s,sa,n+1,256);
	calheight(s,sa,n);
	for(int i=1;i<=n;i++)
		printf("%d ",sa[i]+1);
	puts("");
	for(int i=2;i<=n;i++)
		printf("%d ",height[i]);
} 

评测结果