Ps: 博主在此只是添加一些自己的理解! 而且在学习SAM的时候一定需要理解清楚基础概念, 我会反复强调的

有一部分是摘自陈立杰的报告: 2012-NOI冬令营陈立杰讲稿


自动机的概念:

有限状态自动机的功能是识别字符串,令一个自动机A,若它能识别字符串S,就记为A(S) = True,否则A(S) = False。

自动机由五个部分组成,alpha:字符集,state:状态集合,init:初始状态,end:结束状态集合,trans:状态转移函数

不妨令trans(s,ch)表示当前状态是s,在读入字符ch之后,所到达的状态

如果trans(s,ch)这个转移不存在,为了方便,不妨设其为null,同时null只能转移到null。

null表示不存在的状态

同时令trans(s, str)表示当前状态是s,在读入字符串str之后,所到达的状态

后缀自动机的定义:

给定字符串 s

S的后缀自动机,简记为SAM,是一个能够识别S的所有后缀的自动机。

SAM(x) = True当且仅当x是S的后缀

同时后面可以看出,后缀自动机也能用来识别S所有的子串。

以上摘自陈立杰文章, 不过均是非常重要的基本知识!


分析:

首先, 如果我们来一个字符串 “aabbabd”, 如果用Trie树暴力对其构造的话, 我们的树大概就是长这样的!

Screenshot.png
暴力建树

我们不难看出状态数量是捕获, 但是这些状态代表的状态其实是可以”压缩”的, 也就是说它们之间存在共性.  这就是为什么最后的自动机是长这样的:

2018-07-21 00-45-59屏幕截图.png

 

我们后缀自动机的目的就是使得状态数最小化!

首先, 我们观察一下这一个”aabbabd“的后缀自动机, 我们会发现自动机之中的边所到达的点都是整个字符串的一个子串, 而且我们发现字符串”aabb” 与 “abb” 最后所到达的点都是一个点! 所以这些边其实就好像”导游一样” 把某一些字符串集合在了一起, 因为它们都具有相同的性质! 于是我们就可以将这些引领的边称作”ch” 边!

一些规定与变量

  1. 我们将自动机上的点称之为状态
  2. Right(a) 表示的是字符串a在原串出现的位置为{[l1, r1), [l2, r2) … [ln, rn)} (注意是开区间) 比如Right(“a”) = {2, 3, 6} (我们存的是右端点的位置!)
  3. 我们的s比如是自动机上的一个状态, 那么Right{s} 表示的是所有总串之中Right集合等于Right(s)的字符串, 如出Right等于{5} 的字符串有:{“aabb”, “abb”, “bb”} 其中不包含”b”是因为Right(“b”) = {4, 5, 7}, 然后s的状态所代表的字符串集合就是{“aabb”, “abb”, “bb”}  可根据上图稍微手摸一下!
  4. 我们记状态s代表的字符串集合之中长度范围是[min(s), max(s)] 不难证明字符串都是连续出现的!
  5. ch(s, c) 表示由状态s经过一条ch(c)的边所到达的状态. 也就好比是trans(s, c)

关于上述变量的一些性质:

  • Right(a) 与Right(b) 要么有无交集, 如果有交集的话, Right(b) 与Right(a) 一定是真子集关系, 且a代表的字符串集一定是b代表的字符串集的后缀!

证明:

不妨令max(b) < min(a)

由于a与b的字符串集合不存在交集(根据自动机的性质: trans(init,s) 最后只会达到一个状态) 那么

我们的字符串a, b 出现的样子一定是这样的:

无标题.png

那么我们不难看出 b 的每一个字符串都是a 的字符串的后缀, 而且Right(a) ⊂  Right(b) (真子集关系) 因为不可能是等于, 不然的话 b 这个集合就会包括了a这个字符串集合, 而且我们知道串越短, 出现的位置越多的可能性越大!

无标题.png

观察一下 :

无标题

Right 集合构成的确实是一个树形结构! 我们称它为Parent 树, 而且每一个节点的Right 集合都是孩子节点的Right集合的并∪, 我们的父子关系就是 pre 边维护的东西, 即状态a 的父节点是Right集合能包含Right(a)的最小的一个, 那么pre(a) 指向的就是它!

自动机的构造:

我们考虑增量法(其实就是数学归纳法构造) 

我们考虑现在加入的点为np , 字符为 x,(原字符串为 S, 长度为len) 上次最后加入的点是p,  我们所需要考虑的仅仅只是以 右端点在len+1的后缀!

而且这些后缀就是包含了p , pre(p), pre(pre(p)) 这样的一条链上, 用上我们刚刚说的性质, 因为都是后缀, 而且Right{p} 一定只有len, 即一定会有字符串S在内部, 于是一直向上跳就会枚举到所有的后缀!

然后我们的构造方法是

  1. 如果 p 没有ch(x) 的出边, 就向ch(x) 指向 np, p 跳到pre(p)
  2. 如果 p 有ch(x)的边 , 指向的点为 q !

如果max(p) + 1 = max(q) , 我们就可以将np 连向 q 并终止Add

不然我们就可以考虑拆点, 拆成 q 与 nq , 将 pre(q) 变成 nq , pre(np) 变成nq 就好了

因为拆点的原因是因为q的字符串集合之中有一些字符串的right集合会增加len + 1, 而有一些没有, 所以就会导致冲突! 于是要拆点!

比如:(Right可能不合法, 但是感受一下)

e697a0e6a087e9a2984.png
q的字符串集合为{“AAAAAx”, “AAAAAAx”} , 且Right为{8, 23}

但是假设p={“AAAAA”}, 但是如果有x加入了之后, 我们会发现 字符串”AAAAAx”的Right集合扩充了, 但是”AAAAAAx”的却没有, 于是就会存在冲突了!

手模:

先贺一发别人的图, 之后自己会更新的!

sambt11sambt21sambt31

(未完待续…)

 

Leave a Reply