2012年noi冬令营陈立杰讲稿(SAM后缀自动机)研究.ppt

最简状态后缀自动机 顾名思义，就是状态数最少的后缀自动机，在后面可以证明它的大小是线性的，我们先来看一些性质。 假如我们得到了这个最简状态后缀自动机SAM。 我们令ST(str)表示trans(init,str)。就是初始状态开始读入字符串str之后，能到达的状态。 分析 分析 分析 分析 状态数的线性证明 状态数的线性证明 状态数的线性证明 一些性质 一些性质 关于子串的性质 由于每个子串都必然包含在SAM的某个状态里。 那么一个字符串s是S的子串，当且仅当，ST(s)!=null 那么我们就可以用SAM来解决子串判定问题。 同时也可以求出这个子串的出现个数，就是所在状态Right集合的大小。 关于子串的性质 在一个状态中直接保存Right集合会消耗过多的空间，我们可以发现状态的Right就是它Parent树中所有孩子Right集合的并集，进一步的话，就是Parent树中它所有后代中叶子节点的Right集合的并集。 那么如果按dfs序排列，一个状态的right集合就是一段连续的区间中的叶子节点的Right集合的并集，那么我们也就可以快速求出一个子串的所有出现位置了。 树的dfs序列：所有子树中节点组成一个区间。 线性构造算法 我们的构造算法是Online的，也就是从左到右逐个添加字符串中的字符。依次构造SAM。 这个算法实现相比后缀树来说要简单很多，尽管可能不是非常好理解。 让我们先回顾一下性质 定义和性质的回顾 状态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树。 定义的回顾 一个Right集合和一个长度定义了一个子串。 对于状态s，使得Right(s)合法的子串长度是一个区间，为|[Min(s),Max(s)] Max(Parent(s)) = Min(s)-1。 SMA的状态数量和边的数量，都是O(N)的。 不妨令trans(s,ch)==null表示从s出发没有标号为ch的边， 定义的回顾 每个阶段 每个阶段 每个阶段 每个阶段 每个阶段 每个阶段 每个阶段 接下来考虑节点nq,在转移的过程中,结束位置L+1是不起作用的，所以trans(nq)就跟原来的trans(q)是一样的，拷贝即可。 每个阶段 每个阶段 自此我们圆满的解决了转移的问题。 嘟嘟噜，搞完啦～～ 每个阶段：回顾 我们需要新的算法来解决这个问题 在SPOJ的讨论版中，出题人提到了要使用suffix automaton来解决此题。 * 提到字符串数据结构，大家都会想到这些 * 了解AC自动机的同学都不会陌生， * 如果时间复杂度达到N^2级别，这个数据结构也就没有意义了。 演示插入的过程。 * 说了这么多，如果不能给出一个构造SAM的算法，也没有意义。 * 后缀自动机Suffix Automaton 杭州外国语学校 陈立杰 WJMZBMR 吐槽回答 Q：你是哪里的弱菜？我听都没听说过！ A：我是来自杭州外国语学校的陈立杰，确实是弱菜。 Q：Suffix Automaton？我根本就没有听说过这种数据结构。 A：这个还是有点用处的，等下我会讲的，你就当长知识了吧。 Q：呼噜噜~~~~~~ A：睡好。。。 先让我们看SPOJ上的一道题目 1812. Longest Common Substring II 题目大意：给出N(N = 10)个长度不超过100000的字符串，求他们的最长公共连续子串。 时限：SPOJ上的2s 一个简单的做法 二分答案之后使用哈希就可以在O(LlogL)的时间内解决这个问题。这个做法非常经典就不详细讲了。 看起来很简单。。但是。。。 我们可以看到大部分人都TLE了。。为什么呢？ SPOJ太慢了 SPOJ太慢了 SPOJ太慢了 SPOJ太慢了 SPOJ太慢了 SPOJ太慢了 SPOJ太慢了 新的算法 OI中使用的字符串处理工具 Suffix Array 后缀数组 Suffix Tree 后缀树 Aho-Corasick Automaton AC自动机 Hash 哈希 什么是自动机 有限状态自动机的功能是识别字符串，令一个自动机A，若它能识别字符串S，就记为A(S)=