代码

//include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring> 
#include <set>
#include <map>
#define db double 
#define LL long long
//#define int LL
#define rep(i,x,y) for (int i=x;i<=y;++i)
#define mp make_pair
#define ft first
#define sd second
#define P pair<int ,int >
#define pb push_back 
using namespace std;
const int N  =  2e5+233;
//const int mod = ;
struct Suffix_Array
{
	static const int M=257;
	int rk[N],tp[N],cnt[M],h[N],sa[N],n,m,p,i,j,k;
	char str[N];
	void Init()
	{
		scanf("%s",str+1);
		n=strlen(str+1);
	}
	void Sort()
	{
		memset(cnt,0,sizeof(cnt));
		rep(i,1,n) ++cnt[rk[tp[i]]];
		rep(i,1,m) cnt[i]+=cnt[i-1];
		for (int i=n;i>=1;--i) sa[cnt[rk[tp[i]]]--]=tp[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) rk[i]=str[i],tp[i]=i;
		m=256;Sort();
		for (int w=1;w<=n;w<<=1,m=p)
		{
			for (p=0,i=n-w+1;i<=n;++i) tp[++p]=i;
			rep(i,1,n) if (sa[i]>w) tp[++p]=sa[i]-w;
			Sort(),swap(rk,tp),rk[sa[1]]=p=1;
			for (i=2;i<=n;++i) rk[sa[i]]=cmp(tp,sa[i],sa[i-1],w) ?p :++p;
		}
		for (k=0,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()
{
	S.Init();
	S.SA()	;
	rep(i,1,S.n) printf("%d ",S.sa[i]);puts("");
	rep(i,2,S.n) printf("%d ",S.h[i]) ;
	return 0;	
}

评测结果