后缀自动机

------本文来源于学习陈立杰ppt后的感悟

前言

         本文力争用理性分析的手段,来推测此算法发明者的思维过程, 尝试感受其在设计此算法的时所展现出的思维方式, 力求用数学证明的手段,尽可能多的为读者证明相关结论,建议有其他自动机学习的基础,最好已经学会AC自动机和回文自动机,后缀自动机很难,他 和其他自动机不一样,它的状态更加复杂,一个算法的创作过程很 复杂,学起来当然会感到很难。强烈建议看陈立杰的ppt,看一遍肯定看不懂,仔细看,一遍看不懂看多遍,第一次可能只能看懂几面,第二次可 能就能看懂到十几面了,慢慢的就全懂了。

后缀自动机为什么难?

         后缀自动机是三个自动机里面最难的一个,难的地方不在与编码,在于他背后的数学推导
         想要完全理解后缀自动机,就必须深入理解什么叫自动机,这和AC自动机、回文 自动机不同,因为AC自动机、回文自动机背后的数学推导过于简单。

自动机

         百度百科里面说的很清楚,也很抽象。自动机,是一个五元组,包含字符集,状态集合, 初始状态,结束状态集合,状态转移函数。
         五元组中,有四个包含了"状态"这个名词。难以理解的,正是这个状态。

状态是什么

         此处的状态,其实和动态规划算法中出现的名词"状态",是同一个东西。状态的 本质就是集合,是满足某种条件的所有元素的一个集合体,当然我们很多 时候不好用计算机来储存这样的一个集合体,很多时候我们也不需要去储存他,更多的时候我们只需要储存这个集合体的某一个或者多个性质即可,

自动机的状态

         字符集好理解,状态集合就是自动机中所有的节点,状态转移函数就是自动机中节点之间 的边。初始状态就是自动机中字典树上的根,结束状态就是自动 机之中包含了结束标记的节点。

后缀自动机和后缀数组有关吗?

         后缀自动机是建立在一颗后缀树上的,当然他不像AC自动机来源于KMP算法,不像回文自动机来源于 manacher算法一样,他并不是后缀数组算法的加强。
         一个字符串的后缀树肯定是非常庞大的,n个后缀,如果我们直接把它建立出来,那么空间复杂度和 时间复杂度无疑都是O(n^2),必须优化。
         我们发现后缀树上的很多节点所代表的状态有某些共同点,毕竟他们都是同一个母串的后缀, AC自动机所定义的节点代表的状态指的是:从根到此节点的路径连接成的字符串以及他的所有后缀。后缀自动机在这一点上 根AC自动机有点类似,此处暂时不先说。

我们来创建一个最小状态数的后缀自动机

         我们先假设我们已经建立好了一个后缀自动机,此自动机不一定状态数最少,后缀自动机的存在性就不必证明了。 然后我们尝试分析这个不太完美的后缀自动机,来尝试优化他。

约定一些符号表示

         我们称自动机的初始状态为init,转移函数为trans(state,str),表示状态state经过字符串str的转移后得到的新的状态。 因为是术语,此处暂时不对状态做定义。如果某个状态为结束状态,那么我们用end(state)=true来表示。

将状态形象化,然后造一个暴力的后缀自动机

         我们假设我们建立的后缀自动机,是一棵究极大的,n^2级别状态数量的自动机。我们先来定义此自动机的状态:某个节点 所代表的状态,就是母串的一个子串。显然这不是一个好状态。显然其中的字典树 的根节点root就是初始状态 。

想办法来优化这个暴力的自动机

         我们必须减少状态,然而,一个串的子串数量明显就是平方级别的,根本就没有多余的状态,对此已经无解,必须减少状态数量,我们考虑后缀自动机关心 的是后缀,而不是子串,那么可能存在某些状态,他们在另外一种状态的定义下,是等价的。我们考虑某个状态state,如果存在某个字符串 str,使得end (trans(state,str))=true,那意味着什么?state状态中的元素:子串substring,追加上str,是一个结束状态。

再具体一点,我们来举例子

         母串是abcabcde,考虑他的某个子串abc,显然此子串对应的状态trans(root,"abc")在经历串abcde的转移后得到了结束状态,同时此状态在经历串 de的转移后也可以得到结束状态,也就是说,子串abc对应的状态在经历串abcde或de的转移后可以得到结束状态。

发现了可以优化的地方

         当我们考虑串bc、串c的时候,我们发此案这两个串能够转移到的结束状态根串abc一摸一样,这可不是开玩笑的。如果可能,我们将可以合并串abc、bc、 和c对应的状态,也就是说,trans(root,"abc"),trans(root,"bc"),trans(root,"c")可以用一个状态来表示。我们来仔细研究研究,为什么会发生这种 事情?如果某两个状态trans(root,str1),trans(root,str2)能够转移的结果是完全一样的,那意味着什么?先考虑trans(root,str)能够转移到某个 结束状态,也就是说str+???将会成为母串的后缀。

约定一些符号表示

         right(str)表示字符串str在母串中出现时的所有右端点的集合,suf(index)表示从下标为index开始的后缀,

继续分析

         容易证明状态state=trans(root,str)能转移到的结束状态,就是对于所有在right(str)中的元素x,计算出的状态:trans(state,suf(x+1)) 当right(str1)与right(str2)一摸一样的时候,其能够转移到的结束状态是一摸一样的,因为这只受到right集合的影响。既然一摸一样,有什么理由 不去利用这个优点呢?

开始实现优化

         我们尝试修改状态的定义,尝试把right集合一摸一样的串用一个状态来表示。让笔者来概括一下这个新状态:我们对母串 的每一个子串都统计一下right集合,将子串按照right集合分类,每一类就是一个状态。如无特殊声明,下文的出现的状态将不再指的是原状态 ,而是表示新状态。

证明状态数是线性的

         证明分为两个部分,先证明right集合间的关系只有两种,包含关系和无交集关系,于是right集合间的关系可以用一颗叶子节点最多n个的树来表示。(n是 母串的长度。)再证明此树最多有2n个节点来完成证明。第一部分的证明:考虑串str1,和str2,并假设str2更长,如果str1不是str2的后缀,那么他们的 right集合一定不一样,且没有交集,可以反证,若是后缀,那么str2出现的地方的右端点,也是str1出现的右端点,于是right(str2)是right(str1)的子集 。第二部分的证明很简单,笔者就不再赘述了。
         既然状态数是线性,转移(边的条数)当然也是线性的。

证明状态数是最小的

         此处笔者由于水平原因,实在是无法证明,罪过罪过。

增量法构建最小状态

         所谓增量法,就是一个一个增加的意思,具体一点,如果我们要算f(10),我们先算f(1),通过f(1)来计算f(2),通过f(2)来算f(3)...最后算出f(10),这就是增量法, 他和数学归纳法有点像。第一步,我们拥有一个初始状态:根,第二步,假设我们已经的到了字符串str的一个后缀自动机SAM(str),x是一个字符,我们怎么得到字符串 str+x的后缀自动机呢?考虑这两个字符串的区别,str+x多了一个x,后缀自动机是来识别后缀的,所以SAM(str)以前能够识别的后缀suf的那些状态全部要改,除此之外 没有其他修改的地方。怎么改呢?那些状态在SAM(str)里面确实是结束状态,但是在SAM(str+x)中却不是。但是他们能够向x字符转移,得到新的结束状态。之前证明过 状态是按照right集合来划分的,而right集合有只有两种关系,于是我们发现了一个新的东西,SAM(str)的所有结束状态在right构成的树上是一条链,也就是说right 构成的树不知可以用来证明状态树是线性的,还可以用来帮助我们建设状态。那么我们就把这棵树取出来,叫做parent树。
         在parent树上,如果我们知道了状态trans(root,str)在哪,就可以根据parent树上面的边遍历所有的结束状态,因为这些结束状态的right集合一定包含了len(str) 也就是说他们都是状态trans(root,str)在parent树上面的祖先。

细节处理

         现在我们来总结一下,从自动机SAM(str) 增量构建自动机SAM(str+x),我们需要更改的只是trans(root,str)以及他在parent树上面的所有祖先,容易证明如果状态 q是trans(root,str)的第一个包含字符x转移的状态,那么q的所有祖先都包含了字符x的转移。trans(root,str)到q之间(不包含q)的所有状态都不包含字符x的转移。 可以证明:如果不包含x的转移,我们直接构建一个新的状态p表示trans(root,str+x)状态,此处可以证明他的right集合只有一个元素, 就是len(str+x)。那些不包含x转移的状态,可以直接转移到p,因为那样转移之后的right集合是就是p的right集合。那么我们就一直这样做即可,那么q以及q的祖先呢?他们包含了字符x的转移 但是我们可以直接在那个地方设置一个结束标志吗?这不一定?为什么呢?首先,我们的状态定义是依据right集合的,也就是说right集合一摸一样的,才能用一个状态表示。 如果我们那样做,会造成什么后果呢?节点q向x转移的状态trans(q,x)的right集合是不包含len(str+x)的,我们那样做,会导致right集合扩大。right集合扩大,可能会 导致以前能够用trans(q,x)表示的某些串,不能用trans(q,x)表示了。
         举个例子,abcxabc+x和abcxbc+x,对于第一个,原本abc拥有向x的转移,当时还不是结束标记,当我们加入字符x后我们强行让这个转移变为结束标记,一点问题都没有,abcx 确实是新的结束标记,然而对于第二个,原本bc拥有向x的转移,当时还不是结束标记,当我们加入字符x后,如果还是强行让这个转移变为结束标记,出现问题了,abcx也可以转移到 那里,可是abcx不是串的结束状态。

到底什么时候需要创建新的节点

         我们来思考一下,什么时候那样做是对的。如果无脑加结束标记是对的,那就意味着,以前能够到达trans(q,x)的串,他们的right集合,现在都能够到达len(str+x),我们再一次 思考状态state的意义,相同right集合的串,用同一个状态表示,这些串之间有什么关系吗?如果我们定义max(state)为这个状态能表达的串的最大长度,min(state)表示这个 状态=能表达的串的最小长度,可以证明,这个state能表达的所有串,恰好为max(state)和min(state)之间的所有串,举个例子:如果max(state)为abcdef,min(state)为 def,实际上,state的所有串是:def,cdef,bcdef,abcdef,还可以证明,min(state)=max(fa(state))-1,fa(state)表示在parent树上state的父亲。
         我们不难证明在原串中如果max(q+x)=max(q)+1的时候,无脑加入结束标记是对的,这确保没有比max(q)更大的其他状态能够转移到trans(root,q+x)在这种情况下,直接设置一下 fa(p)=trans(root,q+x),可以证明整个更新到此就已经结束了。
         但是如果不等呢?肯定是不可以那样做的,我们考虑状态到定义,我们发现我们必须重建一个新的状态,来把目前到这个trans(root,q+x)状态分解为两个状态,一个储存串使得max(q'+x)=max(q)+x 另一个储存剩余的,那些东西要移到q'+x去呢?我们发现那些q的祖先中,能够转移到trans(root,q+x)的都要改到q'+x ,如此过后,我们发现现在的情况变得根上一段一摸一样了, 终于,整个后缀自动机构建完成。
struct SAM{//下标从1开始,0作为保留位,用于做哨兵
    //如果没有特殊要求,尽量选择合适的自动机,要算好内存
    //经过hdu1000测试,10000个map大概是10kb,对于1e6的字符串,不建议使用后缀自动机
    typedef map<int,int>::iterator IT;
    static const int MAXN=1e5+10;
    int cnt,last,par[MAXN<<1],len[MAXN<<1];
    map<int,int>trans[MAXN<<1];//map用于字符集特别大的时候,注意这里占内存可能会特别大

    int newnode(int parent,int length){
        par[++cnt]=parent;
        len[cnt]=length;
        trans[cnt].clear();
        return cnt;
    }

    void ini(){
        cnt=0;
        last=newnode(0,0);
    }

    void extend(int c){
        int p=last;
        int np=newnode(1,len[last]+1);//新建状态,先让parent指向根(1)
        while(p!=0&&trans[p].find(c)==trans[p].end()){//如果没有边,且不为空,根也是要转移的
            trans[p][c]=np;//他们都没有向np转移的边,直接连过去
            p=par[p];//往parent走
        }
        if(p!=0){//如果p==0,直接就结束了,什么都不用做,否则节点p是第一个拥有转移c的状态,他的祖先都有转移c
            int q=trans[p][c];//q是p转移后的状态
            if(len[q]==len[p]+1)par[np]=q;//len[q]是以前的最长串,len[p]+1是合并后的最长串,相等的话,不会影响,直接结束了,
            else{
                int nq=newnode(par[q],len[p]+1);
                trans[nq]=trans[q];//copy出q来,
                par[np]=par[q]=nq;//改变parent树的形态
                while(trans[p][c]==q){//一直往上面走
                    trans[p][c]=nq;//所有向q连边的状态都连向nq
                    p=par[p];
                }
            }
        }
        last=np;//最后的那个节点
    }//SAM到此结束

    int count_all_substring(){//本质不同的串,不必调用拓扑排序
        int ret=0;
        for(int i=2;i<=cnt;i++){//不必计算根,因为根太特殊了,它代表的是空串,
            ret+=len[i]-len[par[i]];//每个节点存的串都是唯一的right集合,所以对所有状态求和即可
        }
        return ret;
    }

    int bfn[MAXN<<1],bfn__[MAXN<<1];//辅助数组
    void sort(){//拓扑排序,利用len的特性,len小的肯定是子孙,相同的顶多是兄弟,大的肯定是祖先级别的,
        for(int i=1;i<=cnt;i++)bfn__[len[i]]++;//len的值分布于1到n,对此计数
        for(int i=1;i<=cnt;i++)bfn__[i]+=bfn__[i-1];//统计前缀和
        for(int i=1;i<=cnt;i++)bfn[bfn__[len[i]]--]=i;//bfn[i]是排名为i的节点的编号,i从1开始
    }

    int right[MAXN<<1];//right集合的大小
    void get_right(){//先调用sort得到拓扑序,然后再来这里
        for(int i=bfn[cnt];i!=0;i=par[i])right[i]=1;
        for(int i=cnt;i>=2;i--){//1号节点为根,其实不需要
            int j=bfn[i];
            for(IT it=trans[j].begin();it!=trans[j].end();it++){
                right[j]+=right[it->second];
            }
        }
    }

    //最长公共子串,先对一个串建立后缀自动机,然后让另外一个串在其上面匹配,此函数不要求bfs序以及right集合
    int query_lcs(char*s){
        int ret=0;
        int l=strlen(s+1);
        int cur=1;
        int length=0;
        for(int i=1;i<=l;i++){
            while(cur!=1&&trans[cur].find(s[i])==trans[cur].end()){
                cur=par[cur];
                length=len[cur];
            }
            if(trans[cur].find(s[i])!=trans[cur].end()){
                cur=trans[cur][s[i]];
                length++;
            }
            else{

            }
            ret=max(ret,length);
        }
        return ret;
    }

};