luogu 3809 【模板】后缀排序

题目背景

这是一道模板题。

题目描述

读入一个长度为 n 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n。

输入输出格式

输入格式：

一行一个长度为 n n 的仅包含大小写英文字母或数字的字符串。

输出格式：

一行，共n个整数，表示答案。

输入输出样例

输入样例#1： 复制

ababa

输出样例#1： 复制

5 3 1 4 2

说明

n <= 10^6

题解

后缀自动机怎么后缀排序呢？加入节点的时候记录一下这个点是不是代表后缀。建完以后重建一下后缀树在上面dfs就可以了= =（注意重建的时候是字典序排序，不是拓扑序

这样的做法时间比较优越，是$O(n)$的。但是注意这里的字符集是62，长度是1e6，这样数组就开不下了。。(算了一下最后是544mb)

所以儿子的转移要硬套一层map。。没想到还能卡过去，最后时间4.7s

#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;
}
void add(int x,int y)
{
    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;
    for (int i=sz;i;i--) add(fa[ti[i]],ti[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]);
}