# luogu 3809 【模板】后缀排序

ababa

5 3 1 4 2

n <= 10^6

### 题解

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define N 1000010
using namespace std;
int dis[N<<1],fa[N<<1],pos[N<<1],sa[N<<1],ri[N<<1],up[N<<1],last=1,sz=1,root=1,len,cnt;
char s[N];
map <int,int> ch[N<<1];
struct edge{int to,next;}e[N<<1];
int st[N<<1],tot;
int ge(char ch)
{
if (ch<='9' && ch>='0') return ch-'0';
if (ch<='Z' && ch>='A') return ch-'A'+10;
if (ch<='z' && ch>='a') return ch-'a'+36;
return ch;
}
{
e[++tot].next=st[x];
e[tot].to=y,st[x]=tot;
}
void insert(int x,int y)
{
int now=++sz,pre=last;last=now;
ri[now]=dis[now]=dis[pre]+1,pos[now]=y;
for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
if (!pre) fa[now]=root;
else
{
int q=ch[pre][x];
if (dis[q]==dis[pre]+1)
fa[now]=q;
else
{
int nows=++sz;dis[nows]=dis[pre]+1;
ch[nows]=ch[q];
fa[nows]=fa[q],fa[now]=fa[q]=nows,ri[nows]=ri[q];
for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
}
}
}
int ton[70],ti[N<<1];
void work()
{
for (int i=1;i<=sz;i++) up[i]=ge(s[len+1-ri[i]+dis[fa[i]]]),ton[up[i]]++;
for (int i=1;i<=64;i++) ton[i]+=ton[i-1];
for (int i=1;i<=sz;i++) ti[ton[up[i]]--]=i;
}
void dfs(int now)
{
if (pos[now]) sa[++cnt]=pos[now];
for (int i=st[now];i;i=e[i].next)
dfs(e[i].to);
}
main()
{
scanf("%s",s+1),len=strlen(s+1);
for (int i=len;i;i--)
insert(ge(s[i]),i);
work();dfs(root);
for (int i=1;i<=cnt;i++) printf("%d ",sa[i]);
}