代码

//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <limits>
#include <map>
#include <vector>
#include <queue> 
#define P pair<int ,int >
#define pb push_back
#define LL long long
#define ft first
#define sd second
#define mp(x,y) make_pair(x,y)
#define db double
//#define int LL
using namespace std;
const int N   = 1e5+233;
//const int mod = ;
const int INF =numeric_limits<int >::max();

#define rep(i,x,y) for (int i=x;i<=y;++i)

struct suffix_array
{
	static const int M=300;
	int cnt[M],rk[N<<1],sa[N<<1],h[N<<1],n,m,p,i,j,k,tp[N<<1];
	int *x=rk,*y=tp;
	char str[N<<1];
	void Sort()
	{	
		memset(cnt,0,sizeof(cnt)) ;
		rep(i,1,n) ++cnt[x[y[i]]];
		rep(i,1,m) cnt[i]+=cnt[i-1];
		for (int i=n;i>=1;--i)
		  sa[ cnt[x[y[i]]]--] =y[i];
	}
	int cmp(int *f,int x,int y,int w){return f[x]==f[y]&&f[x+w]==f[y+w];}
	void SA()
	{
		rep(i,1,n) x[i]=str[i],y[i]=i;
		m=256;Sort();
		for (int w=1;w<=n;w<<=1)
		{
			p=0;
			rep(i,n-w+1,n) y[++p]=i;
			rep(i,1,n) if (sa[i]>w) y[++p]=sa[i]-w;
			Sort();
			swap(x,y);
			x[sa[1]]=p=1;
			rep(i,2,n) 
			  x[sa[i]]=cmp(y,sa[i],sa[i-1],w) ?p :++p;
		}
		rep(i,1,n) rk[sa[i]]=i;
		int j,k=0;
		for (int i=1;i<=n;h[rk[i++]]=k)
		  for (k ? --k :0,j=sa[rk[i] -1];  str[j+k]==str[i+k];++k);
	}
}S;

signed main()
{
	scanf("%s",S.str+1);
	S.n=strlen(S.str+1);
	S.SA();
	rep(i,1,S.n)  printf("%d ",S.sa[i]);
	printf("\n");
	rep(i,2,S.n) printf("%d ",S.h[i]);
	return 0;
}

评测结果