emmm,对着陈立杰的ppt,打这篇博客。。。不是很懂,所以你们将就着看吧。。。。

我们先来讲一些定义:

  • 妨令trans(s,ch)表示当前状态是s,在读入字符ch之后,所到达的状态。
  • 同时令trans(s,str)表示当前状态是s,在读入字符串str之后,所到达的状态。
  • 从状态s开始可以识别的字符串,就是所有使得trans(s,x)属于end的字符串,名为Reg(s)

我们定义后缀自动机:(给定字符串S)

  • S的后缀自动机suffix automaton(以后简记为SAM)是一个能够识别S的所有后缀的自动机。
  • 即SAM(x) = True,当且仅当x是S的后缀。
  • 同时后面可以看出,后缀自动机也能用来识别S所有的子串。

由于直接把所有后缀加入Trie树中,节点大概有N^2个,这样太多了,所以我们引入最简状态后缀自动机

  • 我们令ST(str)表示trans(init,str)。就是初始状态开始读入字符串str之后,能到达的状态。
  • 令字符串为S,他的后缀集合为Suf,他的连续子串的集合为Fac
  • 从位置a开始的后缀为Suffix(a),S[l,r)表示区间[l,r)构成的子串,下标从0开始

我们不能对每一个s属于Fac的串都建一个状态,这样存不下,所以我们考虑ST(s)可以识别多少子串,就是Reg(ST(a));字符串x能被识别,仅当x属于Suf。。对于每一个状态s,我们只关心Reg(s);

假设有字符串a在S中的[l,r)范围中出现,那么由于自动机的特点,他就可以识别从r到结尾的后缀;我们假设a在S中出现的集合是{[l1,r1),[l2,r2),…,[ln,rn)};那么Reg(ST(a))就是{Suffix(r1),Suffix(r2),….Suffix(rn)}这个集合。所以我们不妨令Right(x)={r1,r2,…,rn}那么Reg(ST(x))就完全由Right(x)决定了;

由此可知对于两个子串a,b属于Fac,如果Right(a)=Right(b),那么ST(a)=ST(b);所以一个状态s,由所有Right集合是Right(s)的字符串组成。。。(我已经晕了)所以只要给定一个长度,就可以通过Right集合求出字符串。。。因为某些原因我们令s的区间为[Min(s),Max(s)]。。。

接下来我们讲一下为什么要这么写:

这样写的好处是优化了状态数,我们来证明一下,这样的状态数是线性的。。。

我们考虑两个状态a,b,他们的Right集合为Ra,Rb。我们假设Ra和Rb有交集,不妨设r属于RaRb的交集。那么由于a和b表示的子串不会有交集所以[Min(a),Max(a)]和[Min(b),Max(b)]不会有交集假设Max(a)<Max(b),那么a中的所有子串长度都比b中短,由于都是往前算后缀的。那么a的所以串都是b的后缀,所以Ra属于Rb。这样看来两个串的Right集合,要么不相交,要么一个是另一个的真子集。。。

a

从上图我们可以看出Right集合其实构成一个树状结构,我们称它为Parent树。。。易得这个树的大小一定是O(n)的。令一个状态s,我们令fa=Parent(s)表示上面的那个图中他的父亲,那么Right(s)属于Right(fa),而且Right(fa)的大小是其中最小的。考虑长度,s的范围,[Min(s),Max(s)],为什么Min(s)-1不符合要求,肯定是因为出现的地方超过了Right(s),同时随着长度的减小,出现的地方越来越多,那么Min(s)-1就必然属于fa的范围,那么Max(fa)=Min(s)-1;

然后我们来讲一下他的一些性质:

那么令状态数为M,成树中的边最多只有M-1条,接下来考虑非树边。对于一条非树边a→b标号为c
中我们构造:生成树中从根到状态α的路径+(a->b)+b到任意一个end状态。
可以发现这是一条从init到end状态的路径,由于这是一个识别所有后缀的后缀自动机,因此这必然是一个后缀。那么一个非树边可以对应到多个后缀,我们对每个后缀,沿着自动机走,将其对应上经过的第一条非树边。那么每个后缀最多对应一个非树边,同时一个非树边至少被一个后缀所对应,所以非树边的数量不超过后缀数。。。
所以边的数量也不会超过O(N)。。。

子串的性质:

  • 由于每个子串都必然包含在SAM的某个状态里。
  • 那么一个字符串s是S的子串,当且仅当,ST(s)!=null
  • 那么我们就可以用SAM来解决子串判定问题。
  • 同时也可以求出这个子串的出现个数,就是所在状态Right集合的大小。
  • 在一个状态中直接保存Right集合会消耗过多的空间,我们可以发现状态的Right就是它Parent树中所有孩子Right集合的并集,进一步的话,就是Parent树中它所有后代中叶子节点的Right集合的并集。
  • 那么如果按dfs序排列,一个状态的right集合就是一段连续的区间中的叶子节点的Right集合的并集,那么我们也就可以快速求出一个子串的所有出现位置了。
  • 树的dfs序列:所有子树中节点组成一个区间。

讲完了这些,我们开始构造自动机:

我们每次添加一个字符,并且更新当前的SAM使得它成为包含这个新字符的SAM。令当前字符串为T,新字符为x令T的长度为L。中SAM(T)→SAM(Tx)那么我们新增加了一些子串,它们都是串Tx的后缀.Tx的后缀,就是7的后缀后面添一个x/那么我们考虑所有表示T的后缀(也就是 Right集合中包含L)的节点v1,v2,v3)。由于必然存在一个 Right(p)={L}的节点p(ST(T))。那么v1,v2,…,vk由于 Right集合都含有L,那么它们在 Parent/树中必然全是p的祖先。可以使用 Parentp函数找到他们。

同时我们添加一个字符x后,令np表示ST(Tx),则Right(np)={L+1}.不妨让他们从后代到祖先排为v1=p,v2,…,vk=root。考虑其中一个v的 Rights集合=(r1,r2,…,rn=L}。那么在它的后面添加一个新字符x的话,形成新的状态nv的话,只有S[ri]=x的ri那些是符合要求的。

同时在之前我们知道,如果从v出出发没有标号为x的边(我们先不看rn),那v的 Right集合内就没有满足这个要求的ri。那么由于v1,v2,v3的 Right的集合逐渐扩大,如果vi出发有标号为x的边,那么vi+1出发也肯定有。对于出发没有标号为x的边的v,它的 Right集合内只有rn是满足要求的,所以根据之前提到的转移的规则,让它连一条到np标号为x的边。

令vp为v1,v2,…,vk中第一有标号为x的边的状态。考虑vp的Right集合=(r1,r2,…,rn},令 trans(vp,x)=q。那么q的Rght集合就是{ri+1},S[ri]=x的集合(注意到这是更新之前的情况,所以rn是不算的)。注意到我们不一定能直接在q的Right集合中插入L+1.

最后一个是x,用红色画出vp的结東位置上,长度为Max(vp)的串
用蓝色画出q的结東位置上,长度为Max(q)的串。
串: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAx
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAAAAAAAAx
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx
中从这里可以看出,如果在Right(q)中强行插入L+1,会导到致Max(q)变小,而引发一系列的间题。
当然如果Max(q)=Max(vp)+1就不会有这样的问题,直接插入即可,我们只要让 Parent(np)=q,就可以结東这个阶段了。

这个时候,我们注意到q实际上被分成了两份
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAAAAAAAAx
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx
那么我们新建一个节点nq,使 Right(ng)=Riht(q)∩{L+1}。同时可以看出Max(nq)=MX(vp)+1。那么由于 Right(q)是 Right(nq)的真子集,所以 Parent(q))=nq。同时 Parent(np)=nq。并且容易证明 Parent(nq)= Parent(q)(原来的)

接下来考虑节点nq,在转移的过程中结束位置L+1是不起作用的,所以trans(nq)就跟原来的trans(q)是一样的,直接拷贝就好了。。。

接下来,如果新建了节点nq我们还得处理。
回忆:v1,v2,…,vk是所有Right集合包含的节点按后代到祖先排序,其中vp是第一个有标号为x的边的祖先。x是这轮新加入的字符。由于vp,…,vk都有标号为x的边,并且到达的点的Right集合,随着出发点Right集合的变大,也会变大,那么只有一段vp,…,ve,通过标号为x的边,原来是到结点q的。
q=Trans(vp,x);
那么由于在这里q节点已经被替换成了nq,我们只要把vp,…,ve的 Irans(*,x)设为nq即可。

然后转移就写完了。。。

令当前串为T,加入字符为x。令p=ST(T), Right(p)= {Length(T)}的节点。新建np=ST(Tx),Right(np)= {Length(T)+1}的节点。对p的所有没有标号x的边的祖先v, trans(v,x)=np。找到p的第一个祖先vp,它有标号x的边,如果没有这样的
vp,那么 Parent(p)=root,结束该阶段。令q= trans(vp,x),若Max(q)=Max(vp)+1,令 Parent(np)=q,结束该阶段。否则新建节点nq,trans(nq,*)=trans(q,*)。
Parent(nq) = Parent(q) (先前的);    Parent(q) = nq;Parent(np)=nq
对所有trans(v,x) == q的p的祖先v,trans(v,x) 改成nq.

c++ 核心代码。。。

struct State
{
    State *par, *go[26];
    int val;
    State(int _val):
        par(0),next(0),val(_val){
            memset(go,0,sizeof(go));
        }
};
State *root,*last;
void extend(int w)
{
    State *p=last;
    State *np = new State(p->val+1);
    while(p && p->go[w]==0)
        p->go[w]=np,p=p->par;
    if(p == 0)
        np->par =root;
    else
    {
        State *q=p->go[w];
        if(p->val+1==q>val)
            np->par=q;
        else
        {
            State *nq =new State(p->val+1);
            memcpy(nq->go,q->go,sizeof(q->go));
            nq->par = q->par;
            q->par = nq;
            np->par = nq;
            while(p && p->go[w]==q)
                p->go[w] = nq,p = p->par;
        }
    }
    last=np;
}

然后终于搞完了,你们随便看看,然后点个赞就好了。。。

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注