[开新坑]对于后缀自动机的一些理解

感觉单纯地从"后缀自动机"的角度来入手并不是非常合理.因为我们懂得很多"后缀自动机"的性质,但却并不清楚"后缀自动机"在本质上是什么.

让我们从后缀树说起.

[1]后缀Trie

Trie树是一棵有根树,每个节点都代表从根节点到这个节点的路径上的字母顺次连接起来的字符串.

对于一个长度为$n$的字符串,我们用一颗Trie树插入它的所有的后缀.不难发现,这样构造的时空复杂度都是$O(n^2)$.

但是后缀Trie却有一些非常好的性质:例如我们想得到后缀数组,只需进行一次dfs即可.又或是我们想查询一个模式串是否在这个串中出现,令模式串长度为$m$,则我们只需$O(m)$的复杂度便可以解决.

但是这样时空复杂度过高了-QoQ.我们不得不考虑别的解决方法.

[2]后缀树

我们发现后缀Trie上有一些非常长的链.我们考虑对信息进行压缩,但是使得它依然具有后缀Trie的性质.

我们将原有的后缀Trie上的节点分为两类:关键点和非关键点.

形象的说,关键点就是那些链的分叉点,非关键点就是在链中间的点.

我们以串"dbabbaa"为例,看下面的图.

从这幅图来看,白色节点就是非关键点,有色节点就是关键节点.其中红色节点表示一个后缀.

我们考虑的后缀树,事实上仅包含这些有色的关键节点.两个关键点之间的边,便包含着之前路径上的非关键点.

上面这幅图便是串"dbabbaa"的后缀树,至于那些指针是什么?一会再说.

为了建立刚才描述的这颗后缀树,我们依旧可以暴力将$n$个后缀插入Trie树中,只不过需要做一些变化:在产生分叉时新建节点即可.

通过观察我们发现:红色节点只有$n$个,而每一个绿色节点的出现都是在合并红色节点的集合,由于红色节点只有$n$个,也就是说至多被合并$n$次,因此绿色节点只有$O(n)$.因此,我们有后缀树的节点数是$O(n)$级别的.

即便如此,暴力建树的时间复杂度依旧是$O(n^2)$级别的.我们需要寻求更有效率的建树方法.

[3]后缀树的高效构造(只是其中一种能用来说明后缀自动机的方法而已)

这是我们需要介绍刚才图中出现的一些指针了.

我们定义,除了根节点之外,每个节点都有一个$pre$指针,指向将这个节点代表的串的首字母删除后得到的串对应的节点.

刚才图中的指针就是$pre$指针.不过刚才的图是后缀树,我们重新给出在后缀Trie上的$pre$指针:

再定义$pre$的逆指针$tranc$指针.一个点显然不一定只有一个$tranc$指针.令节点$p$的$tranc$指针$tranc(p,x)$指向的字符串表示在节点$p$表示的字符串前面加上一个字符$x$得到的字符串对应的节点.这显然很符合$pre$的逆指针的性质.

这两个指针能够帮助我们高效的构造后缀树.

结合上面的图我们看到,后缀树的压缩信息的方式事实上是将非关键点的信息全部压缩到它的深度最小的关键点儿子上.例如,将从别处指来的$pre$指针指到他的关键点儿子上.将自己的$tranc$指针从自己的关键点儿子指出去.

事实上,我们需要的后缀树仅仅是每个节点的父节点以及$tranc$指针.

我们不妨采用增量法构造一颗后缀树.

假设对于字符串$s[1,n]$,我们得到了$[i+1,n]$的后缀树,考虑我们如何得到$[i,n]$的后缀树.

不妨令字符$i$为$x$.

事实上我们发现只是多出了一个后缀$i$而已,那么我们需要将这个后缀也插入后缀树中.新建一个节点$np$表示这个后缀.

对于后缀树中的每一个节点,我们顺便记录这个节点表示的字符串的长度.

考虑从根节点到表示串$[i+1,n]$的节点到一条路径(链)上的若干个节点,事实上每个节点都表示着一个串$[i+1,n]$的前缀.

我们发现我们需要拓宽这些前缀的$tranc$指针,使得它们能够通过在前面加上一个字符$x$到达一个新的状态.

{1}如果对于链上的每一个点都没有$tranc(x)$的出边,我们自然只需都添加上这条出边就好了.

{2}如果有链上的某个点有$tranc(x)$的出边呢?

假设点$p$是这条链上深度最大的有$tranc(x)$的出边的点,那么显然从根节点到$p$的路径上的所有点必定都有$tranc(x)$的出边.

我们首先让剩下的点都连上$tranc(x)$的出边.

我们令$q=tranc(p,x)$.

Case1:如果$q$原本就在后缀树中,我们只需让$np$的树上的父亲为$q$,便可以结束这个阶段.因为我们考虑一下别的点,貌似都没有什么影响的说.

Case2:如果$q$原本是后缀树中的无用节点.这什么意思?指针不是都指向后缀树中的点吗?而这些点显然应该是原有的关键节点啊!

参见上面谈论的后缀树的压缩方式.可能$q$是被压缩到它的一个关键点儿子上了.我们令它的关键点儿子为$q$,而其自身为$nq$.

下面考虑我们需要对后缀树进行的修改.

首先我们令$nq$的父亲为$q$原来的父亲,同时$q$和$np$的父亲都设为$nq$.这些都是显而易见的.

由于$nq$的关键点儿子是$q$,那么$nq$的$tranc$转移显然应该与$q$相同.否则,$nq$就不至于当做无用节点去掉.所以,我们令$nq$拷贝$q$的$tranc$转移.

让我们通过第三幅图来观察一下在后缀Trie上$pre$指针的某些特性.我们观察一整条链的$pre$指向,我们发现这些指向的节点形成了另外一条链.

那么反过来$tranc$的指针指向的节点也是呈一条链的.

在后缀树上,由于信息被压缩,那么不难发现指针指向的节点是分段的.(有点意识流QoQ,看图就会有体会了吧)

首先$p$的$tranc(x)$指针应该指向$nq$.(否则我们为什么要把它搞出来?)考虑$p$的一段连续原先$tranc(x)$指向$q$的祖先,它们的$tranc(x)$指针都应该指向$nq$.

这是由于一条链的连续性使然.

看起来别的节点大概就没有什么影响了.

蛮清晰吧?

我们能够证明,这样建立后缀树的复杂度是$O(n)$.怎么证明先挖坑.

之前已经证明了后缀树的节点数和边数为$O(n)$.因此,后缀树是一个能够达到输入下界的优秀算法.

[4]后缀自动机

现在终于要开始说后缀自动机啦~~~

明面上来说,一个字符串的后缀自动机能且仅能识别这个字符串的所有后缀.

我们如何识别一个后缀?自然是从头到尾一个字母一个字母在后缀自动机上走啦.若走到了接受节点,那么这个串就是原串的后缀.

这就像是一开始是一个空串,随后一点一点向末尾追加字母一样.

考虑我们后缀树的$tranc$指针都干了什么?我们通过$tranc$指针,是可以实现在串的开头加上一个字母.

假设我们建立一个串的反串的后缀树(逆序后缀树),用原串的一个后缀在后缀树上走,不断地在开头补充字母,最终是能够得到一个前缀的.

这样的话在逆序后缀树上的最后一个节点所在的那一条链都可以算是接受节点.

事实上我们知道一个串的逆序后缀树就等于这个串的后缀自动机.因为我们从识别后缀的这个角度看,二者是等价的.

那么建立一个串的后缀自动机等价于建立这个串的逆序后缀树,也就是我们只需要从前向后插入字符即可.

因此我们欣喜地看到,这样的后缀自动机构造方法是支持在线向末尾插入字符的.

根据我们的理解,后缀自动机上也有一个$tranc$指针,表示向末尾追加字符,和逆序后缀树上的$tranc$指针完全相同.

后缀自动机也是树形结构,结构与逆序后缀树完全相同.

不过,以个人来感觉,把这个结构当成逆序后缀树应当具有更大的可拓展性?

题目的话,有时间再来补充.

upd@2015.01.14 19:50 tag:更新了一些题解的链接

http://wyfcyx.is-programmer.com/posts/76391.html

http://wyfcyx.is-programmer.com/posts/76400.html

http://wyfcyx.is-programmer.com/posts/76423.html