后缀自动机（SAM）学习笔记

发表于 | 分类于 
这是本博客第一篇正经学术贴（严肃脸）

干了三个小时，对后缀自动机有了一点清晰的认识（板子稍后再动手），留存记录，以防止忘光QAQ
（建议阅读者对AC自动机有一定认识）
参考资料：
WJMZMBR于WC 2012的讲稿
chrt的博客 后缀自动机

Q：什么是自动机？

可以识别一类字符串的机器模型？把字符串丢进去就能识别什么的。
有限状态自动机就是识别的串数量有限的自动机。
自动机由五个部分组成，alpha：字符集，state：状态集合，init：初始状态，end：结束状态集合，trans：状态转移函数。
不妨令trans(s,ch)表示当前状态是s，在读入字符ch之后，所到达的状态。
如果trans(s,ch)这个转移不存在，为了方便，不妨设其为null，同时null只能转移到null。
null表示不存在的状态。
同时令trans(s,str)表示当前状态是s，在读入字符串str之后，所到达的状态。
————以上来自WJMZMBR的讲稿
直白一点说，就是一张图，每个点代表一种状态（以下统称点为状态），每条边代表的就是一种状态的转移（即当前字符），那从起始状态出发，到达结束状态走的路径就代表一种“可识别”的字符串。
联想一下AC自动机QwQ

Q: 什么是后缀自动机呢？

顾名思义，就是按照上面的模式，能识别一个串的所有后缀的自动机。
AC自动机就是一部能识别所有添加到trie树里面的串的自动机。

简单概念讲完了，下面我们步入正题。
我们考虑如何构造给定串S的SAM。

Part1:Too Simple

很容易想到一种simple的构造方法：把S的后缀全部拎出来，建立一个AC自动机如何？
图为串“aabbabd”的情况

吼啊，但是考虑下复杂度？
n个后缀都要插入到一个trie树上面，空间复杂度是$O(n^2)$ 的，有点坑啊。
我们考虑下优化。

part2:优化

回到我们一开始的要求，我们要求这个自动机能“识别所有后缀”。
如果记$Reg(x)$为：以状态x为起点能识别的所有串的集合，对应到图中就是这个点走下去能到到达的所有终点。那么根据定义，它能包含一些后缀就行了。
而且很显然，如果存在$Reg(x)=Reg(y)$ ，那么状态x与状态y就是等价的，可以合并为一个状态。
那么，哪些状态可以合并呢？
考虑状态的实际意义：从起点出发，到达一个状态，这条路径代表的就是一个S的子串。
回到那一棵暴力trie树看看：

假如我们从0号出发，依次经过点0-1-2，我们就会得到一个子串“ba”，而如果是走0-1-3-4，得到的子串就是“bba”。
我们注意到，从2、4接下来能走到的部分是完全一样的，我们便可以说：$Reg(2)=Reg(4)$。即，这两个节点是可合并的。
我们还注意到，由于最终状态就是一个后缀，所以当前状态出发能到达的后缀，一定与到达当前状态后子串的位置有关（因为一个后缀有唯一对应的起始位置），如上图，从0节点走到4号节点与2号节点后，子串“ba”与“bba”对应的结束位置都是4（从0开始计数），那么以2，4起点，能到达的终点就是从4开始的后缀，而对于节点5而言，子串“a”的结束位置有三个：{0,1,4}，所以从它出发，可以到达从0,1,4开始的后缀。
所以，对于每个状态x，我们只需记录从起点出发到达这里代表的子串在原串里的出现位置即可知道它的$Reg(x)$ 。
我们定义这个节点对应的子串结束位置的集合为$Right(x)$，如上图中，$Right(5)=\{0,1,4\}$,$Right(2)=Right(4)=\{4\}$。
由于前文提及，$Reg(x)$只和$Right(x)$有关，那么对于所有的$Right(x)$相等的点，我们就可以合并。
下面列举了部分子串的集合，每个子串在trie树中都对应了一个状态：
a: 0,1,4
b: 2,3,5
d: 6
aa: 1
bb: 3
ab: 2,5
……
那么根据上文，我们把每个状态按照right集合分类
如下图，颜色相同的状态表示他们有相同的right。

然后合并，结果如下：

这就是我们最后得到的SAM了O$\omega$O

Part3:证明

这么优化了之后，空间是线性的。
如何证明？
5.4青年节前来填坑~
对于两个不同的状态a,b，它们代表的子串必然不相同。
如果它们的right集合存在交集说明什么呢？
它们的子串存在结束位置相同。这表示必然存在其中一个是另一个的后缀，因为在这个位置同时出现了a,b串的结尾。所以，right集合如果有交集，必然是包含关系。
即任意两个状态之间的关系只有两种：相离与包含。
任意两个不同的right集合也只有两种关系：相离和真包含。
那么这种集合之间的包含关系，我们可以看成一个树，其中祖先包含它的所有儿子，这棵树我们称为“parent树”。
例如：“aabbabd”的包含关系如下：

由于，叶子的right集合一定大小为1，所以总共有n个叶子，因而整棵树的节点个数是线性的。
而最终的SAM的节点个数，就是这棵树的节点个数。
对于状态转移而言，我们对SAM建立一棵生成树，那么其叶子节点一定代表一个后缀。对于非树边，其也对应着叶子的唯一后缀，所以也是线性的。

Part4:实现

代码其实很短，原理上面也给出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int in[1010][26],fa[1010],mx[1010];
int nn,last;
void build(int x){//每次添加一个值为x
	int p=last,np=++nn;
	mx[np]=mx[p]+1;
	while(~p&&!in[p][x])
		in[p][x]=np,p=fa[p];
	if(p==-1)return;
	int q=in[p][x];
	if(mx[q]==mx[p]+1)fa[np]=q;
	else{
		int nq=++nn;mx[nq]=mx[p]+1;
		fa[nq]=fa[q];
		fa[np]=fa[q]=nq;
		for(int i=0;i<26;i++)in[nq][i]=in[q][i];
		while(~p&&in[p][x]==q)in[p][x]=nq,p=fa[p];
	}last=np;
}

确实是很短啊
下面给出解释。
这段代码在线建立了SAM，并维护了两个数组：fa和mx，其中fa表示的是这个状态的节点在Parent树上的祖先对应的节点，mx表示“以此节点为终点的子串的最长长度”
首先，我们的当前节点的mx，就是它上一个位置对应的mx+1 。
然后，考虑哪些点能实现到x的转移，就是right集合里面有上一个位置的那些节点，其中，last的right集合就只有一个，也就是上一个位置，根据parent树的性质，last的祖先们right集合一定都有这个位置，所以一路向祖先走，并建立边。
下面考虑维护fa，也就是parent树上应该在何处插入此节点。
我们找到第一个存在in[p][x]的节点，并记in[p][x]为q。
如果它的mx就等于p+1的话，q就可以作为我们当前插入的节点的fa。
否则新建一个节点nq，让其等价于q，但mx[nq]等于mx[p]+1，并让q成为nq的祖先，然后令当前节点的fa等于nq。
可能有些地方我并没有说清楚啊QAQ，泥萌可以看陈老师的论文。。。
以上。