后缀自动机 Suffix Automaton

Presentation on theme: "后缀自动机 Suffix Automaton"— Presentation transcript:

1 后缀自动机 Suffix Automaton
杭州外国语学校 陈立杰 WJMZBMR

2 吐槽&回答 Q：你是哪里的弱菜？我听都没听说过！ A：我是来自杭州外国语学校的陈立杰，确实是弱菜。
Q：Suffix Automaton？我根本就没有听说过这种数据结构。 A：这个还是有点用处的，等下我会讲的，你就当长知识 了吧。 Q：呼噜噜~~~~~~ A：睡好。。。

3 先让我们看SPOJ上的一道题目 1812. Longest Common Substring II
题目大意：给出N(N <= 10)个长度不超过100000的字 符串，求他们的最长公共连续子串。 时限：SPOJ上的2s

4 一个简单的做法 二分答案之后使用哈希就可以在O(LlogL)的时间内解决这 个问题。这个做法非常经典就不详细讲了。

5 看起来很简单。。但是。。。

6 我们可以看到大部分人都TLE了。。为什么呢？
SPOJ太慢了

7 新的算法 我们需要新的算法来解决这个问题 在SPOJ的讨论版中，出题人提到了要使用suffix automaton来解决此题。

8 OI中使用的字符串处理工具 Suffix Automaton又是什么呢？ Suffix Array 后缀数组 Suffix Tree 后缀树
Aho-Corasick Automaton AC自动机 Hash 哈希 Suffix Automaton又是什么呢？ 提到字符串数据结构，大家都会想到这些

9 什么是自动机 有限状态自动机的功能是识别字符串，令一个自动机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之后，所到达的状态。 了解AC自动机的同学都不会陌生，

10 trans(s,str) Cur = s; For i = 0 to Length(str)-1 Cur = trans(Cur,str[i]); trans(s,str) 就是Cur

11

12 后缀自动机的定义 给定字符串S S的后缀自动机suffix automaton(以后简记为SAM)是一个能 够识别S的所有后缀的自动机。
即SAM(x) = True，当且仅当x是S的后缀 同时后面可以看出，后缀自动机也能用来识别S所有的子 串。

13 状态数量太多了！怎么破？ 最简单的实现 考虑字符串”aabbabd” 我们可以讲该字符串的所有后缀 插入一个Trie中，就像右图那样。
那么初始状态就是根，状态转移 函数就是这颗树的边，结束状态 集合就是所有的叶子。 状态数量太多了！怎么破？ 如果时间复杂度达到N^2级别，这个数据结构也就没有意义了。 演示插入的过程。

14 最简状态后缀自动机 顾名思义，就是状态数最少的后缀自动机，在后面可以证 明它的大小是线性的，我们先来看一些性质。
假如我们得到了这个最简状态后缀自动机SAM。 我们令ST(str)表示trans(init,str)。就是初始状态开始读入字 符串str之后，能到达的状态。

15 分析

16 分析

17 分析

18 分析

19 状态数的线性证明

20 状态数的线性证明 1,2,3,4,5,6,7,8 1,2,3 1 2,3 2 3 4 5 6,7,8 6 7 8

21 状态数的线性证明

22 一些性质

23

24 一些性质

25 关于子串的性质 由于每个子串都必然包含在SAM的某个状态里。 那么一个字符串s是S的子串，当且仅当，ST(s)!=null
同时也可以求出这个子串的出现个数，就是所在状态Right 集合的大小。

26 关于子串的性质 在一个状态中直接保存Right集合会消耗过多的空间，我们 可以发现状态的Right就是它Parent树中所有孩子Right集合 的并集，进一步的话，就是Parent树中它所有后代中叶子 节点的Right集合的并集。 那么如果按dfs序排列，一个状态的right集合就是一段连续 的区间中的叶子节点的Right集合的并集，那么我们也就可 以快速求出一个子串的所有出现位置了。 树的dfs序列：所有子树中节点组成一个区间。

27 线性构造算法 我们的构造算法是Online的，也就是从左到右逐个添加字 符串中的字符。依次构造SAM。
这个算法实现相比后缀树来说要简单很多，尽管可能不是 非常好理解。 让我们先回顾一下性质 说了这么多，如果不能给出一个构造SAM的算法，也没有意义。

28 定义和性质的回顾 状态s，转移trans，初始状态init，结束状态集合end。
母串S，S的后缀自动机SAM(Suffix Automaton的缩写)。 Right(str)表示str在母串S中所有出现的结束位置集合。 一个状态s表示的所有子串Right集合相同,为Right(s)。 Parent(s)表示使得Right(s)是Right(x)的真子集，并且Right(x) 的大小最小的状态x。 Parent函数可以表示一个树形结构。不妨叫它Parent树。

29 定义的回顾 一个Right集合和一个长度定义了一个子串。
对于状态s，使得Right(s)合法的子串长度是一个区间，为| [Min(s),Max(s)] Max(Parent(s)) = Min(s)-1。 SMA的状态数量和边的数量，都是O(N)的。 不妨令trans(s,ch)==null表示从s出发没有标号为ch的边，

30 定义的回顾

31 每个阶段

32 每个阶段

33 每个阶段

34 每个阶段

35 每个阶段

36 每个阶段

37 每个阶段 接下来考虑节点nq,在转移的过程中,结束位置L+1是不起作 用的，所以trans(nq)就跟原来的trans(q)是一样的，拷贝即 可。

38 每个阶段

39 每个阶段 自此我们圆满的解决了转移的问题。 嘟嘟噜，搞完啦～～

40 每个阶段：回顾

41 每个阶段：回顾 否则新建节点nq，trans(nq,*)=trans(q,*) Parent(nq) = Parent(q) (先前的) Parent(q) = nq Parent(np)=nq 对所有trans(v,x) == q的p的祖先v，trans(v,x) 改成nq

42 C++的代码实现

43 C++的代码实现 虽然我讲了这么多 代码还是很好写的

44 让我们实战一下吧 实践出真知！ 实践是检验真理的唯一标准！

45 I.最小循环串 给一个字符串S，每次可以将它的第一个字符移到最后面， 求这样能得到的字典序最小的字符串。 如BBAAB，最小的就是AABBB
考虑字符串SS，我们就是要求SS的长度为Length(S)且字典 序最小的子串，那么我们构造出SS的SAM，从init开始每 次走标号最小的转移，走Length(S)步即可以得到结果。 为什么这样是对的就留给大家作为小思考了。

46 II.SPOJ NSUBSTR 给一个字符串S，令F(x)表示S的所有长度为x的子串中，出 现次数的最大值。求F(1)..F(Length(S)) Length(S) <= 我们构造S的SAM，那么对于一个节点s，它的长度范围是 [Min(s),Max(s)]，同时他的出现次数是|Right(s)|。那么我们 用 |Right(s)|去更新F(Max(s))的值。 同时最后从大到小依次用F(i)去更新F(i-1)即可。 为什么这样是对的也作为小思考。

47 III.BZOJ2555 SubString 你要维护一个串，支持在末尾添加一个字符和询问一个串 在其中出现了多少次这两个操作。 必须在线。
构造串的SAM，每次在后面加入一个字符，可以注意到真 正影响答案的是Right集合的大小，我们需要知道一个状态 的Right集合有多大。

48 III.BZOJ2555 SubString 回顾构造算法，对Parent的更改每个阶段只有常数次，同 时最后我们插入了状态np，就将所有np的祖先的Right集合 大小+了1。 方法1：使用动态树维护Parent树。 方法2：使用平衡树维护Parent树的dfs序列。 这两种方法跟今天的主题无关，不详细讲了。

49 IV:SPOJ SUBLEX 给一个长度不超过90000的串S，每次询问它的所有不同子 串中，字典序第K小的，询问不超过500个。
我们可以构造出S的SAM，同时预处理从每个节点出发， 还有多少不同的子串可以到达。 然后dfs一遍SAM，就可以回答询问了。 具体实现作为小练习留给大家。

50 V:SPOJ LCS 给两个长度小于100000的字符串A和B，求出他们的最长公共连 续子串。 我们构造出A的后缀自动机SAM
对于SAM的每个状态s，令r为Right(s)中任意的一个元素，它代 表的是结束位置在r的，长度在[Min(s),Max(s)]之间的所有子串。 AAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAA 我们不妨对状态s，求出所有B的子串中，从任意r开始往前能匹 配的最大长度L，那么min(L,Max(s))就可以更新答案了。

51 V:SPOJ LCS 我们考虑用SAM读入字符串B。 令当前状态为s，同时最大匹配长度为len
我们读入字符x。如果s有标号为x的边， 那么s=trans(s,x),len = len+1 否则我们找到s的第一个祖先a，它有标号为x的边，令 s=trans(a,x),len=Max(a)+1。 如果没有这样的祖先，那么令s=root,len=0。 在过程中更新状态的最大匹配长度

52 V:SPOJ LCS 注意到我们求的是对于任意一个Right集合中的r，最大的 匹配长度。那么对于一个状态s，它的结果自然也可以作 为它Parent的结果，我们可以从底到上更新一遍。 然后问题就解决了。

53 VI:SPOJ LCS2

54 一些其他的东西 其实不仅仅有Suffix Automaton还有。。 Factor Automaton Suffix Oracle
Factor Oracle Suffix Cactus Oracle的意思是神谕！听起来很强吧。

55 Factor Oracle 一个串的Factor Oracle是一个自动机，可以识别这个串的 所有子串的集合，但也可以识别一些别的乱七八糟的东西。 其实Oracle也有预言的意思，所以这个是不一定准的。 Factor Oracle的构造算法非常的简单，不过我也不知道这 个在OI中有什么用，就不讲了。

56 Queries are welcomed！

57 广告 我会把课件和代码放在我的博客上，地址是：