LG3809 【模板】后缀排序

佚名 6年前 (2019-04-09) 随笔 1194人围观抢沙发百度已收录

题意

题目背景

这是一道模板题。

题目描述

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1： 复制

ababa

输出样例#1： 复制

5 3 1 4 2

说明

$n <= 10^6$

分析

推荐博客：算法学习：后缀自动机转后缀树转后缀数组。

对反串建立后缀自动机，然后用parent树建出后缀树，最后在后缀树上dfs求出后缀数组。

因为后缀自动机的parent树连起来是原串的反向前缀树，所以对反串这样做建立起的就是后缀树。

对反串建立后缀自动机的时候，要额外记录pos数组，表示节点对应的原串中后缀起始位置。这样配合len数组便知道了后缀树上面的边上面的字符。

时间复杂度$O(n)$

代码

字符集包含大小写英文字母或数字，这就非常烦了……用了各种奇技淫巧才卡过这道题。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=2e6+10;
char s[N];
int n;
// SAM
unordered_map<int,int> ch[N];
int pos[N],val[N],len[N],fa[N],last=1,sz=1;
void extend(int c,int po){
    int p=last,cur=last=++sz;
    pos[cur]=po,val[cur]=1,len[cur]=len[p]+1;
    for(;p&&!ch[p].count(c);p=fa[p]) ch[p][c]=cur;
    if(!p) fa[cur]=1;
    else{
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[cur]=q;
        else{
            int clone=++sz;len[clone]=len[p]+1;
            ch[clone]=ch[q];
            fa[clone]=fa[q],pos[clone]=pos[q];
            fa[q]=fa[cur]=clone;
            for(;ch[p].count(c)&&ch[p][c]==q;p=fa[p]) ch[p][c]=clone;
        }
    }
}
// ST
vector<pair<int,int> > e[N];
int sa[N],rank[N],tp;
void dfs(int u){
    if(val[u]) sa[::rank[pos[u]]=++tp]=pos[u];
    sort(e[u].begin(),e[u].end());
    for(auto i:e[u]) dfs(i.second);
}
int main(){
    scanf("%s",s+1),n=strlen(s+1);
    for(int i=n;i>=1;--i) extend(s[i],i);
    for(int i=2;i<=sz;++i) e[fa[i]].push_back(make_pair(s[pos[i]+len[fa[i]]],i));
    dfs(1);
    for(int i=1;i<=n;++i) printf("%d ",sa[i]);
    return 0;
}