后缀自动机

前言

本文力争用理性分析的手段,来推测此算法发明者的思维过程, 尝试感受其在设计此算法的时所展现出的思维方式, 力求用数学证明的手段,尽可能多的为读者证明相关结论,建议有其他自动机学习的基础,最好已经学会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 ,如此过后,我们发现现在的情况变得根上一段一摸一样了, 终于,整个后缀自动机构建完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;

struct SAM{//下标从1开始,0作为保留位,用于做哨兵
//如果没有特殊要求,尽量选择合适的自动机,要算好内存
//经过hdu1000测试,10000个map大概是10kb,对于1e6的字符串,不建议使用后缀自动机
typedef map<int,int>::iterator IT;
static const int MAXN=2e5+10;
int cnt,last,par[MAXN<<1],len[MAXN<<1];
// map<int,int>trans[MAXN<<1];//map用于字符集特别大的时候,注意这里占内存可能会特别大
int trans[MAXN<<1][26];

inline int newnode(int parent,int length){
par[++cnt]=parent;
len[cnt]=length;
// trans[cnt].clear();
for(int i=0;i<26;i++) trans[cnt][i]=-1;
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][c]==-1){//如果没有边,且不为空,根也是要转移的
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来,
for(int i=0;i<26;i++) trans[nq][i]=trans[q][i];
par[np]=par[q]=nq;//改变parent树的形态
while(trans[p][c]==q){//一直往上面走
trans[p][c]=nq;//所有向q连边的状态都连向nq
p=par[p];
}
}
}
last=np;//最后的那个节点
}//SAM到此结束
}sam;