代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
using ull=unsigned long long;
char ch[N];
int n,rk[N],sa[N],ht[N];
ull hsh[N],pw[N],p=131;
bool cmp(int a,int b){
	// if(ch[bl[be[a]]]==ch[bl[be[b]]]){
	// 	int L=min(bl[be[a]]-a,bl[be[b]]-b);
	// 	a+=L,b+=L;
	// }
	// while(a<n&&b<n&&ch[a]==ch[b])a++,b++;
	// if(a>=n)return 1;
	// if(b>=n)return 0;
	// return ch[a]<ch[b];
	int fl=0;
	if(a>b)swap(a,b),fl=1;
	int l=0,r=n-b-1,ans=-1;
	while(r>=l){
		int mid=(l+r)>>1;
		if((hsh[a+mid]-hsh[a-1])*pw[b-a]==hsh[b+mid]-hsh[b-1])ans=mid,l=mid+1;
		else r=mid-1;
	}
	// cerr<<a<<" "<<b<<" : "<<ans<<endl;
	if(b+ans==n-1)return fl;
	return fl^(ch[a+ans+1]<ch[b+ans+1]);
}
int main(){
	cin>>ch;
	n=strlen(ch);
	pw[0]=1;
	for(int i=1;i<n;i++)pw[i]=pw[i-1]*p;
	for(int i=0;i<n;i++)hsh[i]=(ch[i]-28)*pw[i]+hsh[i-1];
	for(int i=0;i<n;i++)sa[i]=i;
	stable_sort(sa,sa+n,cmp);
	for(int i=0;i<n;i++)rk[sa[i]]=i,printf("%d ",sa[i]);
	puts("");
	for(int i=0,k=0;i<n;i++){
		if(rk[i]==0)continue;
		k-=!!k;
		while(ch[i+k]==ch[sa[rk[i]-1]+k])k++;
		ht[rk[i]]=k;
	}
	for(int i=1;i<n;i++)printf("%d ",ht[i]);
	return 0;
}

评测结果