lp3809 【模板】后缀排序

我们考虑一下前缀排序。
很显然可以上一个后缀自动机。按顺序深度搜索输出即可。
那么对于后缀排序，只需要倒着插入然后输出parent树即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 2000005

inline int hsh(char C){
	return 'a'<=C&&C<='z'?C-'a'+36:('A'<=C&&C<='Z'?C-'A'+10:C-'0');
}

int l[MAXN],r[MAXN],nxt[MAXN][62],fa[MAXN],fst[MAXN],bckt[MAXN],a[MAXN];
int loc[MAXN];
char ch[1000005];
int cnt,nw;
int n;

int v[MAXN],to[MAXN],h[MAXN],et=0;
inline void add(int U,int V){
	++et,v[et]=V,to[et]=h[U],h[U]=et;
}

inline void prpr(){
	fa[0]=-1,cnt=nw=0;
}
int p,q,np,nq;
inline void psh(int C,int I){
	np=++cnt;r[np]=l[np]=l[nw]+1;p=nw;nw=np;loc[np]=I;
	while(p>=0&&!nxt[p][C]){
		nxt[p][C]=np;
		p=fa[p];
	}
	if(p==-1){
		fa[np]=0;
		return;
	}
	q=nxt[p][C];
	if(l[p]+1==l[q]){
		fa[np]=q;
		return;
	}
	nq=++cnt;
	l[nq]=l[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq,r[nq]=r[q];
	for(int i=0;i<62;++i){
		nxt[nq][i]=nxt[q][i];
	}
	while(p>=0&&nxt[p][C]==q){
		nxt[p][C]=nq;
		p=fa[p];
	}
}
inline void srt(){
	for(int i=1;i<=cnt;++i){fst[i]=hsh(ch[n-r[i]+1+l[fa[i]]]),++bckt[fst[i]];}
	for(int i=0;i<62;++i){bckt[i]+=bckt[i-1];}
	for(int i=1;i<=cnt;++i){a[bckt[fst[i]]--]=i;}
	for(int i=cnt;i;--i){add(fa[a[i]],a[i]);}
}
int tp=0;
inline void dfs(int X){
	if(loc[X]){
		printf("%d ",loc[X]); 
	}
	for(int i=h[X];i;i=to[i]){
		dfs(v[i]);
	}
}
void init(){
	std::cin>>ch+1;
	n=strlen(ch+1);
	for(int i=n;i;--i){
		psh(hsh(ch[i]),i);
	}
	srt();dfs(0);
	puts("");
	
}

int main(){
	prpr(); 
	init();
	return 0;
}