代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAXN=100005;

int n;
char s[MAXN];

struct Suffix
{
	int x,y,id;
	Suffix(int x=0,int y=0,int id=0):x(x),y(y),id(id){}
	inline bool operator ==(const Suffix &b)const {return x==b.x && y==b.y;}
}a[MAXN],b[MAXN];
int wcnt[29],sa[MAXN],rk[MAXN],height[MAXN];

void buildsa()
{
	int tot=0,k=1;
	for(int i=1;i<=n;i++)wcnt[s[i]-'a']++;
	for(int i=1;i<26;i++)wcnt[i]+=wcnt[i-1];
	for(int i=n;i>0;i--)sa[wcnt[s[i]-'a']--]=i;
	for(int i=1;i<=n;i++)
		if(s[sa[i]]==s[sa[i-1]])rk[sa[i]]=tot;
		else rk[sa[i]]=++tot;
	while(k<=n)
	{
		for(int i=1;i<=n;i++)a[i]=Suffix(rk[i],i+k<=n?rk[i+k]:0,i);
		memset(wcnt,0,sizeof(wcnt));
		for(int i=1;i<=n;i++)wcnt[a[i].y]++;
		for(int i=1;i<26;i++)wcnt[i]+=wcnt[i-1];
		for(int i=n;i>0;i--)b[wcnt[a[i].y]--]=a[i];
		memset(wcnt,0,sizeof(wcnt));
		for(int i=1;i<=n;i++)wcnt[b[i].x]++;
		for(int i=1;i<26;i++)wcnt[i]+=wcnt[i-1];
		for(int i=n;i>0;i--)a[wcnt[b[i].x]--]=b[i];
		tot=0;
		for(int i=1;i<=n;i++)
			if(a[i]==a[i-1])rk[a[i].id]=tot;
			else rk[a[i].id]=++tot;
		k<<=1;
	}
	for(int i=1;i<=n;i++)sa[rk[i]]=i;
	k=0;
	for(int i=1;i<=n;i++)
	{
		if(k)k--;
		for(int t=sa[rk[i]-1];i+k<=n && t+k<=n && s[i+k]==s[t+k];k++);
		height[rk[i]]=k;
	}
}

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    buildsa();
    for(int i=1;i<=n;i++)
    	printf("%d ",sa[i]);
    putchar('\n');
    for(int i=2;i<=n;i++)
    	printf("%d ",height[i]);
    return 0;
}

评测结果