WA90求条

问题讨论区 提高段
1 
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node
{
	long long x;
	int id;
}ans[N],a[N];
int n,sa[N],rk[N],height[N];
string s;
bool cmp(node x,node y)
{
	return x.x<y.x;
}
void calc_sa()
{
	a[0].x=-1;
	sort(a+1,a+1+n,cmp);
	int sum=-1;
	for(int i=1;i<=n;++i)
	if(a[i].x==a[i-1].x) rk[a[i].id]=sum;
	else
	{
		sum++;
		rk[a[i].id]=sum;
	}
	for(int k=1;k<=n;k*=2)
	{
		for(int i=1;i<=n;++i)
		{
			if(i+k>n) a[i].x=1ll*rk[i]*N;
			else a[i].x=1ll*rk[i]*N+rk[i+k];
			a[i].id=i;
		}
		sort(a+1,a+1+n,cmp);
		sum=-1;
		for(int i=1;i<=n;++i)
		if(a[i].x==a[i-1].x) rk[a[i].id]=sum;
		else
		{
			sum++;
			rk[a[i].id]=sum;
		}
	}
}
void calc_height()
{
	int k=0;
	for(int i=1;i<=n;++i) rk[sa[i]]=i;
	for(int i=1;i<=n;++i)
	{
		if(rk[i]==1) continue;
		if(k) k--;
		while(s[i+k]==s[sa[rk[i]-1]+k]) k++;
		height[rk[i]]=k;
	}
}
int main()
{
	cin>>s;
	n=s.size();
	for(int i=0;i<n;++i) a[i+1].x=s[i]-97,a[i+1].id=i+1;
	calc_sa();
	s=" "+s; 
	for(int i=1;i<=n;++i) ans[i]={rk[i],i};
	sort(ans+1,ans+1+n,cmp);
	for(int i=1;i<=n;++i) sa[i]=ans[i].id;
	calc_height();
	for(int i=1;i<=n;++i) printf("%d ",sa[i]-1);
	printf("\n");
	for(int i=1;i<=n;++i) printf("%d ",height[i]);
	return 0;
}