后缀自动机

kgxw0430 2019-03-14 原文

字符串：新算法，新自闭

给定字符串s的后缀自动机是一个接受所有字符串s的后缀的最小DFA（确定性有限自动机或确定性有限状态自动机）。
性质：
- 后缀自动机是一张有向无环图。顶点是状态，边是状态之间的转移。
- 初始状态为$t_0$,它是这张图的源点。
- 每个转移代表一个字母。从一个顶点出发的所有转移都不同。
- 一个或多个状态为终止状态。如果我们从初始状态出发，最终转移到了一个终止状态，所形成的一个串必定是s的一个后缀。
- 后缀自动机是所有满足以上条件的自动机中顶点数最少的一个。
几个小理解：
- 后缀自动机上每一个节点代表了一个endpos等价类，并且从$t_0$走到当前节点形成的子串一定是这个节点所代表的endpos等价类中长度最长的子串。
- 每一条返祖边都对应了parent树上的一条边。且返祖边练的一定是不属于当前endpos等价类的一个最长后缀。
- 在parent树上，父节点一定是子节点的后缀。
- 构图是为了实现，从初始状态走可以访问到s所有的后缀。

TJOI2015

t=0，求本质不同的第k小串。
- 想要保证字典序的一个顺序，那我们肯定是在后缀自动机上搞事情。因为在初始状态转移的时候，可以保证字典序。
- 而后缀自动机上每一个节点维护的是什么？一个节点代表一个等价类，同时它也代表了从初始状态到这个点所形成的一个子串。我们可以维护经过每一个点有多少个串。即以这个子串为前缀有多少个串。设$sum[i]$表示经过i节点的子串数量，如果我们处理出了sum数组，那么直接类似线段树求第K大，二分查找就好了。
- 怎么处理出sum数组？考虑后缀自动机是一张有向无环图，我们按照拓扑序跑一遍是可以求出sum数组的。并且我们知道，一个节点向另一个节点连一条边，那么这个节点的长度一定小于另一个点的长度。因此我们仍然用桶按照长度从小到大排序，倒序处理，和拓扑序是等价的。（注意这个处理与求siz数组的不同）。初始值，sum=siz=1。
t=1，相同的子串出现在不同位置，算作不同子串。那么初始值的时候，siz还是siz，不强制赋值为1就好了。

Coding

#include<bits/stdc++.h>
#define rint register int
#define ll long long
using namespace std;
const int N=1e6+10;
int t,n,tot=1,la=1,siz[N],ne[N][30],fa[N],len[N],c[N],A[N];
char s[N];ll sum[N],k;
void add(int c){
    rint p=la,np=la=++tot;siz[tot]=1;len[tot]=len[p]+1;
    for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=np;
    if(!p) fa[np]=1;
    else{
        rint q=ne[p][c];
        if(len[p]+1==len[q]) fa[np]=q;
        else{
            rint nq=++tot;
            memcpy(ne[nq],ne[q],sizeof(ne[q]));
            fa[nq]=fa[q];
            fa[q]=fa[np]=nq;
            len[nq]=len[p]+1;
            for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=nq;
        }
    }
}
void dfs(int p,int num){
    if(num<=siz[p]) return;
    num-=siz[p];
    for(int i=0;i<26;++i){
        if(sum[ne[p][i]]>=num){
            putchar(i+'a');
            dfs(ne[p][i],num);
            return ;
        }else num-=sum[ne[p][i]];
    }
}
int main(){
    scanf("%s",s+1);
    scanf("%d %lld",&t,&k);
    n=strlen(s+1);
    for(rint i=1;i<=n;++i) add(s[i]-'a');
    for(rint i=1;i<=tot;++i) c[len[i]]++;
    for(rint i=1;i<=tot;++i) c[i]+=c[i-1];
    for(rint i=1;i<=tot;++i) A[c[len[i]]--]=i;
    for(rint i=tot;i>0;--i){
        rint p=A[i];
        siz[fa[p]]+=siz[p];
    }
    for(rint i=1;i<=tot;++i) t==0?(sum[i]=siz[i]=1):(sum[i]=siz[i]);
    siz[1]=sum[1]=0;
    for(rint i=tot;i>0;--i){
        rint p=A[i];
        for(int j=0;j<26;++j) sum[p]+=sum[ne[p][j]];
    }
    if(sum[1]<k) cout<<-1<<endl;
    else dfs(1,k),cout<<endl;
    return 0;
}