代码

#include<iostream>
#include<string.h>
using namespace std;
const int N=100005;
int n,sa[N],rk[N],h[N];
char a[N];
namespace SA{
	int cnt[N],la[N];
	void getsa(){
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;++i)rk[i]=a[i],++cnt[a[i]];
		for(int i=1;i<128;++i)cnt[i]+=cnt[i-1];
		for(int i=n;i;--i)sa[cnt[a[i]]--]=i;
		for(int o=1,now,m=128;o<n;o<<=1){
			memset(cnt,0,sizeof(cnt));
			now=0;
			for(int i=1;i<=n;++i)++cnt[rk[i]];
			for(int i=n-o+1;i<=n;++i)la[++now]=i;
			for(int i=1;i<=n;++i)
			if(sa[i]>o)la[++now]=sa[i]-o;
			for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
			for(int i=n;i;--i)sa[cnt[rk[la[i]]]--]=la[i];
			m=0;
			swap(la,rk);
			for(int i=1;i<=n;++i)
				if(la[sa[i]]==la[sa[i-1]]&&la[sa[i]+o]==la[sa[i-1]+o])rk[sa[i]]=m;
				else rk[sa[i]]=++m;
			if(m==n)break;
		}
	}
	void getht(){
		for(int i=1,o=0,la;i<=n;++i){
			o=max(0,o-1);
			la=sa[rk[i]-1];
			while(a[la+o]==a[i+o])++o;
			h[rk[i]]=o;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>(a+1);
	n=strlen(a+1);
	SA::getsa();
	SA::getht();
	for(int i=1;i<=n;++i)
		cout<<sa[i]<<" ";
	cout<<'\n';
	for(int i=2;i<=n;++i)
		cout<<h[i]<<" ";
	cout<<'\n';
	return 0;
}

评测结果