代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int NN=(N<<1)+5;
int n,m=127;
int rk[NN];
int oldrk[NN];
int sa[N];
int id[N];
int cnt[N];
int height[N];
int key[N];
int main()
{
	cin.tie(0)->sync_with_stdio(false);
	cout.tie(0)->sync_with_stdio(false);
	string s;
	cin>>s;
	n=s.size();
	s=" "+s;
	int p=0;
	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
	for(int i=1;i<=n;i++)oldrk[i]=rk[i];
	for(int i=1;i<=n;i++)
	{
		if(oldrk[sa[i]]!=oldrk[sa[i-1]])p++;
		rk[sa[i]]=p;
	}
	for(int w=1;w<n;w<<=1)
	{
		m=p;
		p=0;
		
		for(int i=n;i>n-w;i--)id[++p]=i;
		for(int i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;
		
		for(int i=1;i<=n;i++)key[i]=rk[id[i]];
		
		for(int i=0;i<=m;i++)cnt[i]=0;
		for(int i=1;i<=n;i++)cnt[key[i]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[key[i]]--]=id[i];
		
		p=0;
		for(int i=1;i<=n;i++)oldrk[i]=rk[i];
		for(int i=1;i<=n;i++)
		{
			int x=sa[i],y=sa[i-1];
			if(oldrk[x]!=oldrk[y]||oldrk[x+w]!=oldrk[y+w])p++;
			rk[sa[i]]=p;
		}
		if(p==n)break;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<sa[i]<<" ";
	}
	for(int i=1,k=0;i<=n;i++)
	{
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]-1]+k])k++;
		height[rk[i]]=k;
	}
	cout<<endl;
	for(int i=2;i<=n;i++)
	{
		cout<<height[i]<<" ";
	}
	cout<<endl;
	return 0;
}

评测结果