代码

#include<algorithm>
#include<cstring>
#include<cstdio>
#define mxn 1000010
#define mxm 2000010
using namespace std;
int rt,tp,str,len,cnt,p[mxm],fa[mxm],ln[mxm],trs[mxm][40],son[mxm][40];
int sa[mxn],height[mxn];
char s[mxn];
int build(int u,int c,int i)
{
	int v,x=++tp;
	ln[x]=ln[u]+1,p[x]=i;
	for(;u&&!trs[u][c];trs[u][c]=x,u=fa[u]);
	if(!u) fa[x]=rt;
	else if(ln[v=trs[u][c]]==ln[u]+1) fa[x]=v;
	else
	{
		fa[++tp]=fa[v];p[tp]=p[v];ln[tp]=ln[u]+1;fa[x]=fa[v]=tp;
		for(int i=0;i<36;++i) trs[tp][i]=trs[v][i];
		for(;u&&trs[u][c]==v;trs[u][c]=tp,u=fa[u]);
	}
	return x;
}
int f(int x)
{
	if(x>='a') return x-'a';
	else x-'0'+26;
}
int dfs(int u)
{
	int v,ans=0;
	if(p[u]+ln[u]==len) sa[++cnt]=p[u]+1,ans=cnt;
	for(int i=0;i<36;++i)
		if(v=son[u][i])
		{
			v=dfs(v);
			height[v]=ln[u];
			if(!ans) ans=v;
		}
	return ans;
}
int main()
{
	scanf("%s",s);len=strlen(s);
	rt=tp=str=1;
	for(int i=len-1;i>=0;--i) str=build(str,f(s[i]),i);
	for(int i=2;i<=tp;++i) son[fa[i]][f(s[p[i]+ln[fa[i]]])]=i;
	dfs(rt);
	for(int i=1;i<=cnt;++i) printf("%d ",sa[i]);
	puts("");
	for(int i=2;i<=cnt;++i) printf("%d ",height[i]);
	puts("");
	return 0;
}

评测结果