对于后缀自动机的一丢丢理解

佚名 6年前 (2018-09-27) 算法 2181人围观抢沙发百度已收录

对于后缀自动机的一丢丢理解

好久没更博客了，写一篇证明我还没有退役

如果有错误请大佬们纠正。

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

后缀自动机是一种可以读进一个字符串的所有后缀的有限状态自动机，由于一个子串本质上就是一个后缀的前缀，后缀自动机也能读进所有子串，所以后缀自动机常用于处理子串问题，它的功能比后缀数组更强大。

一些概念

\(endpos:\)一个子串在原串中出现位置(专指结束位置)的集合(注意:是集合)

\(longest:\)一个节点所能代表的最长的字符串(我们一般只记录长度,下面说的所有\(longest\)也都是指长度)

\(shortest:\)一个节点所能代表的最短的字符串

\(child[c]:\)在一个节点后面加上字符c所能转移到的自动机上的节点

\(parent:\)在后缀自动机中，每一个节点代表着\(endpos\)集合相同的一些串，显然，这些串一定是其中最长串的一个后缀，并且长度是连续的，由于更短的后缀可能在更多位置出现，所以它们的\(endpos\)集合不一样，不会在同一节点，其中最长的不属于这个节点的后缀属于的节点就是这个节点的\(parent\),可能有点抽象，举个例子;

对于串:\(aabbabc\)

子串\(ab\)的\(endpos\)集合是{3,6},而子串\(ab\)的一个后缀\(b\)的\(endpos\)集合为{3,4,6},此时串\(ab\)所在的节点不能代表串\(b\),而串\(b\)又是\(ab\)的后缀中最长的不能被代表的串，所以\(ab\)所在的节点的\(parent\)就是\(b\)所在的节点.

显然\(parent\)不会成环，而每个节点都有\(parent\),所以所有\(parent\)最终会构成一颗树，叫做\(parent\)树。

构造

采用增量构造。假设已经建好了前\(n-1\)个字符的后缀自动机，现在要添加第\(n\)个字符。

相当于对整个串的所有后缀都添加一个字符形成新的串。

所以我们只需要对于代表整个串的节点不断跳\(parent\)去构造

如果没有这个串出现，我们就直接新增这个串

如果已经有这个串出现，否则我们可能需要新建节点

看代码感性理解一下(看时好好回忆\(parent\)树的性质)

我知道不一定能看懂构造(确实比较抽象),所以背模板吧，基本上都是这样写的

多做题理解性质就会慢慢知道为啥要这么建了

/*
fa表示parent树上的父亲，len表示longest的长度,p表示上次的终止节点，np表示新建的节点

q,nq与p,np类似，但是解释起来比较麻烦，所以就咕咕咕了.
*/
void insert(int c){
    int p=last,np=last=++cnt;len[np]=len[p]+1;endpos[np]=1;
    while(p&&!ch[c][p])ch[c][p]=np,p=fa[p];
    if(!p)fa[np]=1;
    else {
        int q=ch[c][p];
        if(len[p]+1==len[q])fa[np]=q;
        else {
            int nq=++cnt;
            for(int i=0;i<26;++i)ch[i][nq]=ch[i][q];
            len[nq]=len[p]+1;fa[nq]=fa[q];
            fa[q]=fa[np]=nq;
            while(p&&ch[c][p]==q)ch[c][p]=nq,p=fa[p];
        }
    }
}

//合并endpos，这里只统计endpos集合的大小,如果需要知道具体是多少就需要线段树合并,或者set启发式合并

queue<int>Q;
void solve(){
    for(int i=2;i<=cnt;++i)deg[fa[i]]++;
    for(int i=2;i<=cnt;++i)if(!deg[i])Q.push(i);
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        endpos[fa[u]]+=endpos[u];//上面说过，一个节点在parent树上的儿子的endpos没有交，所以直接简单相加即可
        if(!(--deg[fa[u]]))Q.push(fa[u]);
    }
}