1、后缀自动机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)
2、的时间内解决这个问题。这个做法非常经典就不详细讲了。,看起来很简单。但是。,我们可以看到大部分人都TLE了。为什么呢？,SPOJ太慢了SPOJ太慢了SPOJ太慢了SPOJ太慢了SPOJ太慢了SPOJ太慢了SPOJ太慢了,新的算法,OI中使用的字符串处理工具,Suffix Array 后缀数组 Suffix Tree 后缀树Aho-Corasick Automaton AC自动机Hash 哈希,Suffix Automaton又是什么呢？,什么是自动机,有限状态自动机的功能是识别字符串，令一个自动机A，若它能识别字符串S，就记为A(S)=True，否则A(S)=False。自动机由五个部分组成，
3、alpha：字符集，state：状态集合，init：初始状态，end：结束状态集合，trans：状态转移函数。不妨令trans(s,ch)表示当前状态是s，在读入字符ch之后，所到达的状态。如果trans(s,ch)这个转移不存在，为了方便，不妨设其为null，同时null只能转移到null。null表示不存在的状态。同时令trans(s,str)表示当前状态是s，在读入字符串str之后，所到达的状态。,trans(s,str),Cur = s;For i = 0 to Length(str)-1Cur = trans(Cur,stri);trans(s,str) 就是Cur,后缀自动机的定义
4、,给定字符串SS的后缀自动机suffix automaton(以后简记为SAM)是一个能够识别S的所有后缀的自动机。即SAM(x) = True，当且仅当x是S的后缀同时后面可以看出，后缀自动机也能用来识别S所有的子串。,最简单的实现,考虑字符串”aabbabd”,我们可以讲该字符串的所有后缀插入一个Trie中，就像右图那样。那么初始状态就是根，状态转移函数就是这颗树的边，结束状态集合就是所有的叶子。,状态数量太多了！怎么破？,最简状态后缀自动机,顾名思义，就是状态数最少的后缀自动机，在后面可以证明它的大小是线性的，我们先来看一些性质。假如我们得到了这个最简状态后缀自动机SAM。我们令ST(s
5、tr)表示trans(init,str)。就是初始状态开始读入字符串str之后，能到达的状态。,分析,分析,分析,分析,状态数的线性证明,状态数的线性证明,状态数的线性证明,一些性质,一些性质,关于子串的性质,由于每个子串都必然包含在SAM的某个状态里。那么一个字符串s是S的子串，当且仅当，ST(s)!=null那么我们就可以用SAM来解决子串判定问题。同时也可以求出这个子串的出现个数，就是所在状态Right集合的大小。,关于子串的性质,在一个状态中直接保存Right集合会消耗过多的空间，我们可以发现状态的Right就是它Parent树中所有孩子Right集合的并集，进一步的话，就是Paren
6、t树中它所有后代中叶子节点的Right集合的并集。那么如果按dfs序排列，一个状态的right集合就是一段连续的区间中的叶子节点的Right集合的并集，那么我们也就可以快速求出一个子串的所有出现位置了。树的dfs序列：所有子树中节点组成一个区间。,线性构造算法,我们的构造算法是Online的，也就是从左到右逐个添加字符串中的字符。依次构造SAM。这个算法实现相比后缀树来说要简单很多，尽管可能不是非常好理解。让我们先回顾一下性质,定义和性质的回顾,状态s，转移trans，初始状态init，结束状态集合end。母串S，S的后缀自动机SAM(Suffix Automaton的缩写)。Right(st
7、r)表示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的边，,定义
8、的回顾,每个阶段,每个阶段,每个阶段,每个阶段,每个阶段,每个阶段,每个阶段,接下来考虑节点nq,在转移的过程中,结束位置L+1是不起作用的，所以trans(nq)就跟原来的trans(q)是一样的，拷贝即可。,每个阶段,每个阶段,自此我们圆满的解决了转移的问题。嘟嘟噜，搞完啦,每个阶段：回顾,每个阶段：回顾,否则新建节点nq，trans(nq,*)=trans(q,*)Parent(nq) = Parent(q) (先前的)Parent(q) = nqParent(np)=nq对所有trans(v,x) = q的p的祖先v，trans(v,x) 改成nq,C+的代码实现,C+的代码实现,虽然
9、我讲了这么多代码还是很好写的,让我们实战一下吧实践出真知！实践是检验真理的唯一标准！,I.最小循环串,给一个字符串S，每次可以将它的第一个字符移到最后面，求这样能得到的字典序最小的字符串。如BBAAB，最小的就是AABBB考虑字符串SS，我们就是要求SS的长度为Length(S)且字典序最小的子串，那么我们构造出SS的SAM，从init开始每次走标号最小的转移，走Length(S)步即可以得到结果。为什么这样是对的就留给大家作为小思考了。,II.SPOJ NSUBSTR,给一个字符串S，令F(x)表示S的所有长度为x的子串中，出现次数的最大值。求F(1).F(Length(S)Length(S
10、) = 250000我们构造S的SAM，那么对于一个节点s，它的长度范围是Min(s),Max(s)，同时他的出现次数是|Right(s)|。那么我们用|Right(s)|去更新F(Max(s)的值。同时最后从大到小依次用F(i)去更新F(i-1)即可。为什么这样是对的也作为小思考。,III.BZOJ2555 SubString,你要维护一个串，支持在末尾添加一个字符和询问一个串在其中出现了多少次这两个操作。必须在线。构造串的SAM，每次在后面加入一个字符，可以注意到真正影响答案的是Right集合的大小，我们需要知道一个状态的Right集合有多大。,III.BZOJ2555 SubString
11、,回顾构造算法，对Parent的更改每个阶段只有常数次，同时最后我们插入了状态np，就将所有np的祖先的Right集合大小+了1。方法1：使用动态树维护Parent树。方法2：使用平衡树维护Parent树的dfs序列。这两种方法跟今天的主题无关，不详细讲了。,IV:SPOJ SUBLEX,给一个长度不超过90000的串S，每次询问它的所有不同子串中，字典序第K小的，询问不超过500个。我们可以构造出S的SAM，同时预处理从每个节点出发，还有多少不同的子串可以到达。然后dfs一遍SAM，就可以回答询问了。具体实现作为小练习留给大家。,V:SPOJ LCS,给两个长度小于100000的字符串A和B
12、，求出他们的最长公共连续子串。我们构造出A的后缀自动机SAM对于SAM的每个状态s，令r为Right(s)中任意的一个元素，它代表的是结束位置在r的，长度在Min(s),Max(s)之间的所有子串。AAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAA我们不妨对状态s，求出所有B的子串中，从任意r开始往前能匹配的最大长度L，那么min(L,Max(s)就可以更新答案了。,V:SPOJ LCS,我们考虑用SAM读入字符串B。令当前状态为s，同时最大
13、匹配长度为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。在过程中更新状态的最大匹配长度,V:SPOJ LCS,注意到我们求的是对于任意一个Right集合中的r，最大的匹配长度。那么对于一个状态s，它的结果自然也可以作为它Parent的结果，我们可以从底到上更新一遍。然后问题就解决了。,VI:SPOJ LCS2,一些其他的东西,其实不仅仅有Suffix Automaton还有。Factor AutomatonSuffix OracleFactor OracleSuffix CactusOracle的意思是神谕！听起来很强吧。,Factor Oracle,一个串的Factor Oracle是一个自动机，可以识别这个串的所有子串的集合，但也可以识别一些别的乱七八糟的东西。其实Oracle也有预言的意思，所以这个是不一定准的。Factor Oracle的构造算法非常的简单，不过我也不知道这个在OI中有什么用，就不讲了。,Queries are welcomed！,广告,我会把课件和代码放在我的博客上，地址是：http:/
