浅谈对后缀自动机的一点理解

标签： 后缀自动机

后缀自动机

自动机

要想了解后缀自动机，首先得了解自动机。
例如AC自动机，AC自动机可以识别一个字符串为其所匹配的前缀。
而我们今天所介绍的后缀自动机则是识别一个字符串为自动机串的子串。
在接下来的描述中为了方便，简称\(SAM\)。

暴力实现

我们知道字典树有着优良的时空复杂度，并且可以支持识别一个字符串的前缀。
如果我们将串中的所有后缀插入进字典树，那么就可以实现这个自动机的功能。
不过，由于忽视了后缀的这个性质，总点数高达\(O(n^2)\)。
即使如此，字典树的存储方式还是有一个优点：减少了不必要的重复存储。

优化状态

我们先设\(ST(a)\)代表从初始节点转移字符串a所到的状态。

考虑如何设置状态来减少状态的数量。
首先，对于相同的子串，我们没有必要浪费空间。
字典树是把前缀都放在一起存，那么我们是不是可以另辟蹊径，把后缀都存在一起呢？
一个子串可以表示成一个后缀的前缀，或是前缀的后缀，我们暴力实现就是利用了前者的这个特点。
如果我们把其看做一个前缀的后缀，会不会有更加方便的存法呢？
我们现在状态记录的是一个后缀集合。
对于一个字符串s，我们设\(R(s)\)为\(s\)在\(S\)的位置集合的右端点 $ {r_1,r_2,r_3......,r_k} $
如果对于两个串，\(R(s)=R(t)\)，那么这两个串我们就存在一起，十分方便。
乍一看复杂度还是很鬼，如果直接这么存的话。
因为我们还是记录下了每一个不等价的串。

接下来给出一个定理，可以优化掉大部分的状态。

定理一：对于长度分别为\(l,r\)串\(s\),\(t\),,如果\(R(s)=R(t)\)，那么对于\(l<=x<=r\)的长度为\(x\)的串,总有|R(s)|个满足他们的R集合等于\(R(s)\).

这个结论很显然，但是也很有用。

它告诉了我们，一个状态真正有用的是\(R(s)\)集合对应了一个长度区间\([l,r]\)。这两者可以共同表示这个后缀集合。
在长度区间中的任意长度的后缀，他们的\(R(s)\)集合都是相同的。

接下来我们证明，状态数一定是O(n)个的。
形象的理解的话，首先\(R(\varnothing)=\{1,.....n\}\)。
接下来我们任意加入一些字符（属于集合S）,可以把\(R(\varnothing)\)分成若干个不同的集合\(R(a),R(b),R(c).......\)
对于这些集合，我们再加入字符（当然得到的那个字符串必须是\(S\)的子串）。
当然有时候加入字符并不会使得\(R\)变小，但是这样的同时也不会使得状态数增加。
但是一旦使其变小，就会分裂成多个状态或是使某些元素消失。
分裂最多只会进行n-1次，而消失会进行n次。
所以状态数是\(O(n)\)的。

可以看见，上面的情况是由于一个定理。

定理二：两个\(R\)集合两两不相交或一个为一个的真子集。

接下来我们来证明这个定理。
首先两个集合肯定不相等，然后如果两个R集合相交，那么一个肯定为另一个的后缀，那么这就是真子集了。

从形象的角度理解，貌似这些状态构成了一个树状的东西，我们称之为parent树。
如果对于一个状态x，他的\(R _ x\)对应的区间为\([l_x,r _x]\)。
那么肯定可以找到一个状态y,他的\(R _y\)对应的区间为\([l _y,r _y]\),并且\(r _y=l _x-1\)
那么我们令\(x.parent=y\).并且y所对应的后缀集合一定是x的后缀集合中的后缀。
在让我们形象的来理解parent树。
假如一个状态x,\(R _x\)对应的区间\([l _x,r _x]\)中仅有\(R _x=\{r _x\}\)
那么我们可以想象出一个长度为\(r _x\)的串s,这个串s一开始是S的前缀，我们不断地去掉s的前端，我们发现减到长度为\(l _x-1\)时，这个串竟然在前面出现过，那么集合\(R\)是不是会变化，那么对应了一个新的状态.一直这样下去，我们最后会减到\(\varnothing\)，也就是空串。
是不是对parent树有了新的理解？

再介绍一个东西，叫做\(trans\)函数，\(trans(s,c)\)代表从状态s加上一个字符c所得到的新状态。
这个的性质不是很多，而且很好理解，就不多谈了。
另外，对于一个状态p我们其实只需要记录对应区间中的r,因为l为p.parent.r+1。

构造方法

我们采用在线的增量构造方法。
如果原来的字符串是s，那么p代表包含整个字符串s的状态。
加入的字符是x。
新设np为包含sx的状态。
那么如果\(trans(p,x)==null\)，那么\(trans(p,x)=np，p往上跳parent\)。
如果一直没有值，那么np.parent显然为root.

如果有，令\(q=trans(p,x)\)。
如果\(q.r=p.r+1\),那么我们直接令\(np.parent=q\)
如果没有，现在p.r+1的地方的\(R_x\)会多一个后缀出来，这时候就需要新构造一个状态出来，更新\(R\)。
具体实现可以参照代码，十分好理解。

int tot=1,last=1;
struct Node
{
    int ch[26];
    int fa,len;
}t[MAX<<1];
void add(int x)
{
    int p=last,np=last=++tot;
    t[np].len=t[p].len+1;
    while(p&&!t[p].ch[c])t[p].son[c]=np,p=t[p].fa;
    if(!p)t[np].fa=1;
    else
    {
        int q=t[p].ch[c];
        if(t[p].len+1==t[q].len)t[np].fa=q;
        else
        {
            int nq=++tot;
            t[nq]=t[q]; t[nq].len=t[p].len+1;
            t[q].fa=t[np].fa=nq;
            while(p&&t[p].ch[x]==q)t[p].ch[x]=nq,p=t[p].fa;//向上把所有q都替换成nq
        }
    }
}