后缀自动机学习总结

网上还是有很多教程的。

感觉有个不错的教程这里但是是毛子的。

也可以看看clj的讲稿这里，我觉得没有毛子讲的好。

我这里就主要讲讲重要的思想，也就是一些启发的地方。

首先是自动机的定义。度娘定义

其实和AC自动机差不多，你给它一个串或者字符，它会转移到一个状态。有些串是可接受的，有些是不可接受的，区别就是最后转移到的状态时是合法状态。

AC自动机接受的是一组字符串。也就是说给定某个字符串它会转移到一个end状态。后缀自动机，顾名思义，就是接受一个字符串的所有后缀。

这样的话套用AC自动机的思路，就是找个Trie树把所有后缀往里面一放，这样期望的空间复杂度就是$O(n^2)$的。但是假如我们倒着往里面放，匹配的时候倒着匹配一下，就会发现是个链，感觉很zz。

那岂不是完成了后缀自动机的所有功能？其实并不是，因为后缀自动机的主要的功能是它可以接受那个字符串的所有子串。这样裸的建Trie树空间是$O(n^2)$。但是后缀自动机把空间复杂度优化到了$O(n)$。

我们先不考虑那些概念上的东西，先说下它是怎么存储信息而优化了这么大的空间的。和Trie树不一样，$SAM$(后缀自动机简写)是个DAG，也就是从起始节点开始到某个点可以有很多条路径，所以一个节点可以表示很多个状态。也就是假如直接dfs整个DAG，是可以找到所有子串的。

下面就讲下一些概念

首先是每个点代表了一个状态，这个状态的值就是从起始态到这个点的每一条路径所代表的子串。但是为什么这一个点可以代表很多个子串呢？因为他们有一些共同的性质。这个性质就是它们的$Right$集相同。$Right$集又是什么呢？(下文中，总字符串为：$S$，一个子串为$s$。。

$Right$集： 对于$S$的任何一个子串s，$Right(s)$为一个集合，该集合包含$s$在$S$里面所有出现区间的终点。比如子串$s$在$S$中出现了$k$次，有$s = S[l_1, r_1) = S[l_2, r_2) = \cdots = S[l_k, r_k)$，则$Right(s) = \{r_1, r_2, ……, r_k\}$。

也就是说$Right$集是此状态代表的子串们在原串中的结束位置的并集。所以它还有个性质：一个状态$Right$集合的大小就是这个点所代表子串在原串中的出现次数。

然后就是每个状态都会有个$Parent$指针。定义就是对于一个状态$i$，$Parent_i$表示在$Right$集合包含$i$的$Right$集合的状态中，集合中元素个数最少的那个状态。

现在考虑一个东西，我们有了$Right$集合，该怎么推出一个子串呢？答案是子串长度！如果知道长度$len$，很容易知道$S[r – len, r)$这个子串；如果知道所有的长度，就能确定所有的子串。显然的是，能符合条件的字符串长度应该是一个连续的区间，可以用$[max(s), min(s)]$表示。

可能还是不怎么好理解，可以接着分析下

1.对于一个串$S$，它的一个子串$s$可以在$S$中出现若干次，而$s$的若干个结尾位置的并集就是那个可以表示子串$s$的状态$i$的$Right$集合，将这个集合记为$Right(i)$。

2.如果我们对$s$进行一种操作，每次操作去掉$s$的第一位，设若干次操作后得到的字符串为$s’$，$s’$必然为$S$的后缀，且在进行操作次数较少时，有可能$s’$和$s$的$Right$集合相等。这样记下操作前的长度和操作后第一次$Right$集变化的长度，也就是这个区间的$min、max$。而当$Right$集合发生变化时，一定只会增加一些元素。

3.于是对于$Right$集合相同的字符串，表示它们的状态所能够进行的转移必然也是相同的，因此，他们在$SAM$的$DAG$中，后继的节点也可以重复使用，这就是$SAM$节约空间的原理。

4.对于两个子串$a$和$b$，设$a$的$Right$集合为$Right(a)$，$b$的$Right$集合为$Right(b)$，状态$i_a$可以表示$a$，状态$i_b$可以表示$b$。若$Right(a)$是$Right(b)$的真子集，则$b$必然是$a$的后缀，且在$Parent$树中，$i_b$定为$i_a$的祖先。

主要概念就大概这些了，考虑下如何建立一个$SAM$：

1.先考虑在$O(n^2)$地建立后缀树时，在得到关于一个字符串$S$的后缀树后，可以极快地构建关于$S+x$的后缀树（只需要在结束每个结束节点标号为$x$的边指向的节点定义为新的结束节点即可。

2.而$SAM$是一棵压缩成DAG的后缀树。不妨假设它也有这个性质。

3.我们来考虑如何进行这个[修改结束节点]的操作。

1) 对于可以表示整个串$S$的节点$i$，它在$Parent$树上的祖先必然都可以表示$S$的后缀，因此要对这条链上的节点进行修改；

2) 在发现某个祖先节点已经有了$x$这个儿子时，并不能直接对像在Trie树上一样直接对这个节点进行操作，因为这是DAG，这个儿子可能是公用的，如果直接修改的话，可能会影响其他节点的信息。

3) 此时，可以判断一下若进行修改是否会有信息丢失，若有则新建一个儿子节点，来单独记录这个结束信息，并且因为不能影响它后续的访问，将原有儿子节点的转移信息全部复制到新建的节点中。若有信息丢失，则应为max集合变小（详见clj的ppt），因此在判断时只需要对比当前冲突节点及其儿子的max值。

4) 同样的，$Parent$树上的父子关系也需要进行更新。

4.关于$Right$集合大小的计算，在赋初值的时候只需要给新增节点部分的赋值为1，$Right$集合大小完全可以从儿子到父亲加上去。
只有最后加入的点会赋值为1的原因，是只有那里会有新出现的一个$Right$集合的元素。而这个值并不存在于当前节点子树中的任一节点的$Right$集合中。

这样每次加入一个字符都会新加一个或两个点，所以空间复杂度就是$O(n)$的。开$2n$的空间就可以了。

Talk is cheap,see the code.

#include <cstdio>
#include <cstring>
#define N 100010
using namespace std;
int dis[N<<1],fa[N<<1],ch[N<<1][26],sz=1,root=1,last=root;
char s[N];
void insert(int x)
{
    int pre=last,now=++sz;last=now;//找到代表全串的那个节点，在后面建个新的节点
    dis[now]=dis[pre]+1;//更新一下max
    for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;//找Parent树上有没有这个儿子
    if (!pre) fa[now]=root;//没有的话Parent直接定成起始节点
    else
    {
        int q=ch[pre][x];//找到了一个祖先
        if (dis[q]==dis[pre]+1)
            fa[now]=q;//max没有变小
        else
        {
            int nows=++sz;dis[nows]=dis[pre]+1;//新建一个节点，更新max
            memcpy(ch[nows],ch[q],sizeof ch[q]);//先把所有q的信息都过继到新点上
            fa[nows]=fa[q],fa[now]=fa[q]=nows;//更新下父子关系
            for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;//更新与冲突节点有关的转移
        }
    }
}
main()
{
    scanf("%s",s+1);int len=strlen(s+1);
    for (int i=1;i<=len;i++) insert(s[i]-'a');
}

感觉很难讲清楚。。转一个有图的把= =

http://hi.baidu.com/myidea/item/142c5cd45901a51820e25039

就是这个人的。。但是百度空间已经炸了，找了好久才找了一个

upd:做完题后自己写了个更好理解的这儿

+++++++++++++++++++++++++++++++++++++++++++++++++

这个例子就是aabbabd,以此构造后缀自动机(请耐心看,因为前面几步没有体现算法)

有几点要记得:

1.由一个接受态沿Parent往前走所到的状态也是接受态

2.一个节点及其父辈的代表的串有相同的后缀

1.首先神马都没有:

此时后缀只有一个就是空串:

红字表示此节点代表最长串的长度,一个节点可能代表多个串

2.现在构建”a”的自动机,就是下面这样

现在后缀变成了这样:

3.然后以上为基础构建”aa”的自动机

现在想一下,由S或者说0号节点可以接受的后缀为空串和”a”这两个,那么现在要将”aa”和”a”这两个后缀更新到后缀自动机中,那么1号节点的后缀”a”就要加入一个字符”a”,而空串也要加入字符”a”

也就是所有之前的后缀都要在后面加入一个字符”a”.

但是由于1号节点之前所代表的后缀”a”和1的Parent所代表的后缀(空串)+”a”代表的一样,所以,无需更新1及之前的可接受态

如下图:

自动机就变成了如下:

3.更新自动机变成”aab”自动机

同上加所有接受态也要调整,就是在后面加上”b”字符:

这时,由于1,2节点无法代表三个后缀的任意一个,所以除空串的所有后缀都由3代替

这时3号节点和0号节点为接受态.

自动机成了这样:

具体过程是这样的:

S1:新建节点3

S2:找到最后一个后缀也就是最后一个接受态是节点2

S3:2号节点直接连向3,表示插入后缀”aab”

S4:向上找2的Parent,1号节点,向3连边,表示插入后缀”ab”

S5:找到S,连边,表示插入后缀”b”.

S6:没有其他接受态了,那么3的上一个接受态为S,Parent[3]=S

4:更新成”aabb”的自动机

同理,在所有接受态后加上字符”b”

不过由于接受态0(S)的转移”b”已经存在,那么,由于不能破坏原来的中间态的转移,只能新建一个节点,来代替接受态0(S)的转移节点

自动机成了这样:

找到0(S)时,发现转移”b”已经有节点占了,所以新建节点5,将3号所有信息Copy(包括Parent),然后更新len值,就是node[5]->len=node[5]->parent->len+1,所以5号节点可以代表后缀空串(0号代表的串)+字符”b”=后缀”b”,节点3成了中间态,所以将节点为原接受态的节点指向3的转移改为指向5,这时,我们发现指向3的原接受态节点一定是当前节点0(S)及当前未访问的原接受态节点,所以可以直接沿着Parent往上更新.

然后节点5的Parent及祖先加入了现在的接受态

再次重申一点:一个节点及其父辈的代表的串有相同的后缀,且代表串长度递减,由于5号节点是接受态,所以他的父辈也是接受态,同时反过来也一样,与任意接受态拥有相同后缀的长度小于当前节点的未访问节点一定是当前节点的父辈,如与5号节点有相同后缀的长度小于5号节点的未访问的节点一定是5号的父辈,一定可以作为接受态.

因此为了维护这个性质,我们应该将3号节点的父亲重定义为5

到这里基本上应该明白了

就将剩下的构造过程放出来:

代码什么的如下:

插入一个节点:

意义:

当前新建节点为np,最后的接受态为tail,接受态指针p,pool是内存池,就是一个很大的数组,2*n的空间吧

init就是0号节点

Step 1:建立节点np,p指向tail,np的len更新

Step 2:沿着Parent寻找第一个有转移冲突的接受态节点并沿途更新转移

Step 3:

如果找不到,np的Parent更新为init.

如果正好冲突的节点长度为当前接受态节点那么np的Parent赋为冲突的节点.

否则,新建节点r,Copy冲突节点所有信息,更新r->len=p->len+1,将冲突节点的Parent和np的Parent赋为r,再往前更新与冲突节点有关的转移.

至此结束……….

个人感觉应该表达还算清楚吧(=.=)……

++++++++++++++++++++++++++++++++++++++++++++++++

感觉就是这样了。。后续还有很多题要做= =