精华内容
下载资源
问答
  • 后缀自动机 SAM

    2021-01-06 15:33:58
    SAM 是 DFA 确定性有限状态自动机,是一张 DAG 有向无环图。结点为 状态 ,边被为状态间的 转移。 图存在一个虚拟结点 SSS ,称作 初始状态 ,其它各结点均可从 SSS 出发到达。 每个 转移 都标有一些字母。从一个...
  • 陈立杰2012年冬令营的演讲稿,讲解了后缀自动机的原理,实现方法与应用。
  • 后缀自动机

    2013-03-16 11:52:15
    后缀自动机 陈立杰
  • 后缀自动机详解

    万次阅读 多人点赞 2017-03-26 11:34:54
    后缀自动机   后缀自动机(单词的有向无环图)——是一种强有力的数据结构,让你能够解决许多字符串问题。 例如,使用后缀自动机可以在某一字符串中搜索另一字符串的所有出现位置,或者计算不同子串的个数——这...

    原论文(俄文)地址:suffix_automata

     

    后缀自动机

     

    后缀自动机(单词的有向无环图)——是一种强有力的数据结构,让你能够解决许多字符串问题。

    例如,使用后缀自动机可以在某一字符串中搜索另一字符串的所有出现位置,或者计算不同子串的个数——这都能在线性

    时间内解决。

      直觉上,后缀自动机可以被理解为所有子串的简明信息。一个重要的事实是,后缀自动机以压缩后的形式包含了一个长度

    为n的字符串的所有信息,仅需要O(n)的空间。并且,它能在O(n)时间内被构造(如果我们将字母表的大小k视作常数,否则就

    是O(n*logk))。

      历史上,Blumer等人于1983年首次提出了后缀自动机的线性规模,然后在1985-1986年,人们提出了首个线性时间内构建

    后缀自动机的算法(Crochemore,Blumer等)。在文末链接处查看更多细节。

      后缀自动机在英文中被称作“suffix automaton”(复数形式:suffix automata),单词的有向无环图——"direcged acyclic

    word graph"(简写为“DAWG”)。

     

     

    后缀自动机的定义

    定义.对给定字符串s的后缀自动机是一个最小化确定有限状态自动机,它能够接收字符串s的所有后缀。

     

     

    下面解释这一定义:

    ·        后缀自动机是一张有向无环图,其中顶点是状态,而边代表了状态之间的转移。

    ·        某一状态t_0被称作初始状态,由它能够到达其余所有状态。

    ·        自动机中的所有转移——即有向边——都被某种符号标记。从某一状态出发的诸转移必须拥有不同的标记。(另一方面,

    状态转移不能在任何字符上)。

    ·        一个或多个状态被标记为终止状态。如果我们从初始状态t_0经由任意路径走到某一终止状态,并顺序写出所有经过边的

    标记,你得到的字符串必然是s的某一后缀。

    ·        在符合上述诸条件的所有自动机中,后缀自动机有这最少的顶点数。(后缀自动机并不被要求拥有最少的边数)

    后缀自动机的最简性质

    最简性——后缀自动机的最重要性质是:它包含了所有s的子串的信息。换言之,对于任意从初始状态t_0出发的路径,如果我们

    写出所经过边上的标记,形成的子串必须是s的子串。相应地,s的任意子串都对应一条从初始状态t_0出发的路径。

    为了简化说明,我们称子串“匹配”了从初始状态出发的路径,如果该路径上的边标记组成了这一子串。相应地,我们称任意路径

    “匹配”某一子串,该子串由路径中边的标记组成。

     后缀自动机的每个状态都引领一条或多条从初始状态出发的路径。我们称这个状态有若干匹配这些路径的方法。

     

    构建后缀自动机的实例

    下面给出一些对简单的字符串构建后缀自动机的例子。

     初始状态被记作t0,终止状态用星号(*)标记。

     

    s=""

     

    s="a"

     

     

     

    s="aa"

     

    s="ab"

     

    s="aba"

     

     

     

    s="abb"

     

     

     

    s="abbb"

     

     

     

     

    一个线性时间构建后缀自动机的算法

    在我们描述构建算法之前,有必要介绍一些新的概念和简要的证明,它们对理解后缀自动机的概念十分重要。

     

    结束位置endpos,它们的性质及与后缀自动机的联系:

    考虑字符串s的任意非空子串t。我们称终点集合endpos(t)为:s中所有是t出现位置终点的集合。

    我们称两个子串t_1和t_2“终点等价”,如果它们的终点集合一致:endpos(t_1)=endpos(t_2)。因此,所有s的非空子串可

    以根据终点等价性分成若干类。

     事实上对后缀自动机,终点等价字符串仍然保持相同性质。换句话说,后缀自动机中状态数等价于所有子串的终点等价类

    个数,加上初始状态。每个状态对应一个或多个拥有相同终点集合的子串。

      我们将这一陈述作为假定,然后描述一个基于此假设的,线性时间构建后缀自动机的算法——正如我们不久后将会看到的,

    所有后缀自动机的必须性质,除最小性(即最少顶点数),都将被满足(最小性由Nerode产生,见参考文献)。

     关于终点集合,我们给出一些简单但重要的事实。

     

    引理1.两个非空子串u和v(length(u)<=length(v))是终点等价的,当且仅当u在字符串s中仅作为v的后缀出现。

     

    证明是显然的。

     

    引理2.考虑两个非空子集u,w(length(u)<=length(w))。它们的终点集合不相交,或者endpos(w)是endpos(u)的子集。进一

    步地,这取决于u是否是w的后缀:

     

     

    证明.假设两个集合endpos(u)和endpos(w)有至少一个公共元素,这就意味着字符串w和u在同一位置结束,即u是w的后缀。

    因此,在字符串w的每次出现的终点u都会出现,这就意味着endpos(w)包含于endpos(u)。

     

    引理3.考虑一个终点等价类。将该等价类中的子串按长度递减排序。排序后的序列中,每个子串将比上一个子串短,从而是

    上一个字串的后缀。换句话说,某一终点等价类中的字符串互为后缀,它们的长度依次取区间[x,y]内的所有数。

     

    证明.考虑这个终点等价类。如果它只包含一个子串,那么引理3的正确性显然。假设现在子串的个数多于一个。

     

    根据引理1,两个不同的终点等价子串总满足一个是另一个的严格后缀。因此,在同一终点等价类中的子串不可能有相同的长

    度。

     令w较长,u是等价类中的最短子串。根据引理1,u是w的严格后缀。考虑w任意一个长度为[length(u),length(w)]之间的后缀,

    由引理1,显然它在终点等价类中。

     

    后缀链接

    考虑一个状态v≠t_0.就我们目前所知,有一个确定的子串集合,其中元素和v有着相同的终点集合。并且,如果我们记w是其

    中的最长者,其余子串均是w的后缀。我们还知道w的前几个后缀(按照长度降序)在同一个终点等价类中,其余后缀(至少包括

    空后缀)在别的终点等价类中。令t是第一个这样的后缀——对它我们建立后缀链接。

      换言之,v的后缀链接link(v)指向在不同等价类中的w的最长后缀。

     在此我们假设初始状态t_0在一个单独的终点等价类中(仅包含空字符串),并且endpos(t_0)={-1,...,length(s)-1}。

     

    引理4.后缀链接组成了一棵以t_0为根的树。

     

    证明.考虑任意状态v≠t_0.后缀链接link(v)指向的状态所对应的字符串长度严格小于它本身(根据后缀链接的定义和引理3)。

    因此,沿着后缀链接移动,我们将早晚到达t_0,它对应一个空串。

     

    引理5.如果我们将所有合法的终点集合建成一棵树(使得孩子是父母的子集),这棵树将和后缀链接构成的树相同。

     

    证明.终点集合能构成一棵树这一事实由引理2得出(两个终点集合要么不相交,要么一个包含另一个)。

     

    我们现在考虑任意状态v≠t_0,及其后缀链接link(v)。根据后缀链接的定义和引理2得出:

    endpos(v)endpos(link(v))

    这和上一引理证明了我们的断言:后缀链接树和终点集合树相同。

     

    这里是一个后缀链接的例子,表示字符串"abcbc"

     

     

     

     

    小结

    在学习具体算法之前,总结上面积累的知识,并引入两个辅助符号。

     

    ·        s的所有子串可以按照它们的终点集合被分成等价类。

    ·        后缀自动机由一个初始状态t_0和所有不同的终点等价类所对应的状态组成。

    ·        每个状态v对应一个或多个字符串,我们记longest(v)是其中最长者,len(v)是其长度。我们记shortest(v)是这些字符串中

    的最短者,其长度为minlen(v)。

    ·        该状态对应的所有字符串是longest(v)的不同后缀,并且包括[minlen(v),len(v)]之间的所有长度。

    ·        对每个状态v≠t_0定义的后缀链接指向的状态对应longest(v)的长度为minlen(v)-1的后缀。后缀链接形成一棵以t_0为根的

    树,而这棵树事实上是所有终点集合的树状包含关系。minlen(v)和link(v)的关系表示如下:minlen(v)=len(link(v))+1.

    ·        如果我们从任意节点v_0开始沿后缀链接移动,我们早晚会到达初始状态t_0.在此情况下,我们得到了一系列不相交的区

    间[minlen(v_i),len(v_i)],其并集是一个连续区间。

     

    一个构建后缀自动机的线性时间算法

    我们下面描述这个算法。算法是在线的,即,逐个向s中加入字符,并适当地对当前的自动机进行修改。

     为了达到线性空间的目的,我们将只存储每个状态的len,link的值,以及转移列表。我们并不支持标记终止状态(我们将

    展示如果需要,如何在后缀自动机构建完毕后加上这些标记)。

     最初自动机由一个状态t_0组成,我们称之为0状态(其余状态将被称作1,2,...)。对此状态,令len=0,为方便起见,将link

    值设为-1(指向一个空状态)。

     因此,现在的任务就变成了实现向当前字符串末尾添加一个字符c的操作。

    下面我们描述这一操作:

     

    ·       1. 令last为对应整个字符串的状态(最初last=0,在每次字符添加操作后我们都会改变last的值)。

    ·        2.建立一个新的状态cur,令len(cur)=len(last)+1,而link(cur)的值并不确定。

    ·       3. 我们最初在last,如果它没有字符c的转移,那就添加字符c的转移,指向cur,然后走向其后缀链接,再次检查——如果没

    有字符c的转移,就添加上去。如果在某个节点已有字符c的转移,就停止,并且令p为这个状态的编号。

    ·        4.如果“某节点已有字符c的转移”这一事件从未发生,而我们来到了空状态-1(经由t_0的后缀指针前来),我们简单地令link(cur)=0,

    跳出。

    ·        5.假设我们停在了某一状态q,是从某一个状态p经字符c的转移而来。现在有两种情况:len(p)+1=len(q)或不然。

    ·        6.如果len(p)+1=len(q),那么我们简单地令link(cur)=q,跳出。

    ·        7.否则,情况就变得更加复杂。必须新建一个q的“拷贝”状态:建立一个新的状态clone,将q的数据拷贝给它(后缀链接,以及

    转移),除了len的值:需要令len(clone)=len(p)+1.

    ·        8.在拷贝之后,我们将cur的后缀链接指向clone,并将q的后缀链接重定向到clone。

    ·        9.最终,我们需要做的最后一件事情就是——从p开始沿着后缀链接走,对每个状态我们都检查是否有指向q的,字符c的转移,

    如果有就将其重定向至clone(如果没有,就终止循环)。

    ·        10.在任何情况下,无论在何处终止了这次添加操作,我们最后都将更新last的值,将其赋值为cur。

    如果我们还需要知道哪些节点是终止节点而哪些不是,我们可以在构建整个字符串的后缀自动机之后找出所有终止节点。对此我们

    考虑对应整个字符串的节点(显然,就是我们储存在变量last中的节点),我们沿着它的后缀链接走,直到到达初始状态,并且将

    途径的每个节点标记为终止节点。很好理解,如此我们标记了字符串s所有后缀的对应状态,也就是我们想要找出的终止状态。

     

    在下一节中我们从细节上考虑算法的每一步,并证明其正确性。

    这里我们仅注意一点:每个字符的添加会导致向自动机中添加一个或两个状态。因此,状态数显然是线性的。 

    转移数量的线性性,以及算法的线性时间复杂度较难理解,它们将在下面被证明,位于算法正确性的证明之后。

     

    算法的正确性证明

    ·        我们称转移(p,q)是连续的,如果len(p)+1=len(q)。否则,即len(p)+1<len(q)时,我们称之为不连续转移。

    ·        正如在算法描述中可以看到的那样,连续转移和不连续转移导致了算法流程的不同分支。连续转移)被如此命名是因为,自第

    一次出现后,它们将保持不变。相反,不连续转移可能会在向字符串中添加新字符的过程中被改变(可能会改变该边指向的状态)。

    ·        为了避免歧义,我们称s是我们已经构建了自动机的字符串,它正准备添加当前字符c。

    ·        算法开始时我们创建了新状态cur,它将匹配整个字符串s+c。我们之所以必须新建一个状态的原因是显然的——在添加新字

    符后,出现了一个新的终点等价类——一类以新字符串s+c的末尾为结尾的子串。

    ·        在创建新状态后,算法从和整个字符串s匹配的状态开始,沿着后缀链接移动,在途中试图添加指向cur的,字符c的转移。但

    我们只会在不和已存在转移冲突的情况下添加新的转移,因此一旦我们遇到了一个字符c的转移,我们就必须立刻停止。

    ·        最简单的情形——如果我们来到了空状态-1,向途中所有节点添加了字符c的转移。这就意味着字符c在字符串s中先前未曾出

    现。我们成功地添加了所有的转移,只需要记下状态cur的后缀链接——它显然必须等于0,因为这种情况下cur匹配字符串s+c的一

    切后缀。

    ·        第二种情况——当我们进入一个已存在的转移(p,q)时。这意味着我们试图向字符串中添加字符x+c(其中x是字符串s的某一后

    缀,长度为len(p)),且该字符串先前已经被加入了自动机(即,字符串x+c已经作为子串包含在字符串s中)。因为我们假设字符

    串s的自动机已被正确构建,我们并不应该添加新的转移。
    然而,cur的后缀链接指向哪里有一定复杂性。我们需要将后缀链接指向一个长度恰好和x+c相等的状态,即,该状态的len值必

    须等于len(p)+1.但这样一种情况可能并不存在:在此情况下我们必须添加一个“分割的”状态。

    ·        因此,一种可能的情形是,转移(p,q)变得连续,即,len(q)=len(p)+1.在这种情况下,事情变得简单,不必再进行任何分割,

    我们只需要将cur的后缀链接指向q。

    ·        另一种更复杂的情况——当转移不连续时,即len(q)>len(p)+1.这意味着状态q不仅仅匹配对我们必须的,长度len(p)+1的子串

    w+c,它还匹配一个更长的子串。我们不得不新建一个“分割的”状态q:将子串分割成两段,第一段将恰在长度len(p)+1处结束。

    如何实现这个“分割”呢?我们“拷贝”一个状态q,将其复制为clone,但参数len(clone)=len(p)+1.我们将q的所有转移复制给clone,

    因为无论如何我们不想改变经过p的路径。从clone出发的后缀链接总是指向q原先的后缀链接,而且q的后缀链接将指向clone。

    在拷贝之后,我们将cur的后缀链接指向clone——我们拷贝它就是为了干这个的。

     最后一步——重定向一些指向q的转移,将它们改为指向clone。哪些转移必须被重定向?只需要重定向那些匹配所有w+c的后

    缀的。即,我们需要持续沿着后缀链接移动,从p开始,只要没有到达空状态-1或者没有到达一个状态,其c的转移指向不同于q的

    状态。

     

    证明操作个数是线性的

     

    首先,我们曾经说过要保证字母表的大小是常数。否则,那么线性时间就不再成立:从一个顶点出发的转移被储存在B-树中,

    它支持按值的快速查找和添加操作。因此,如果我们记字母表的大小是k,算法的渐进复杂度将是O(n*logk),空间复杂度O(n)。但

    是,如果字母表足够小,就有可能牺牲部分空间,不采用平衡树,而对每个节点用一个长度为k的数组(支持按值的快速查找)和一

    个动态链表(支持快速遍历所有存在的键值)储存转移。这样O(n)的算法就能够运行,但需要消耗O(nk)的空间。

    因此,我们假设字母表的大小是常数,即,每个按字符查询转移的操作、添加转移、寻找下一个转移——所有这些操作我们都

    认为是O(1)的。

     如果我们观察算法的所有部分,会发现其中三处的线性时间复杂度并不显然:

     

    ·        第一处:从last状态开始,沿着后缀链接移动,并且添加字符c的转移。

    ·        第二处:将q复制给新状态clone时复制转移。

    ·        第三处:将指向q的转移重定向到clone。

    我们使用众所周知的事实:后缀自动机的大小(状态和转移的数目)是线性的。(对状态个数是线性的证明来自算法本身,对于

    移个数是线性的证明,我们将在下面给出,在实现算法之后。)。

      那么显然第一处和第二处是渐进线性的,因为每次操作都会增加新的状态和转移。

      仍然需要估算第三处总的线性复杂度——在每次添加字符时我们将指向q的转移重定向至clone。

     我们不妨关注shortest(link(last))。注意到,在沿着后缀链接上溯的过程中,当前节点的shortest的长度总是严格变小。

     显然,在向s中添加新字符之前,shortest(link(last))的长度不小于shortest(p)的长度,因为link(last)至多是p。尔后假设我们由q

    拷贝得到了节点clone,并试图从p沿后缀链接上溯,将所有通往q的转移重定向为通往clone。设v是shortest(当前节点),在clone刚

    刚建立完成后,v=short(p)。然后,在每次沿后缀链接上溯时,v的值都会变小,而如果当前节点存在经过字符c通往q的转移,就意

    味着q对应的字符串集合中包含v+c,也意味着clone包含的字符串集合中包含v+c。换言之,我们为clone包含的字符串集合找到了一

    个更短的元素,即减少了short(clone)的长度。

    在“向s中添加新字符”的整个流程结束后,有link(last)=link(cur)=clone。根据上面的讨论,新的shortest(link(last))的长度变小(或

    保持不变),而且这一长度减小的值和上溯的操作数同阶。

     综上,shortest(link(last))作为s一个后缀的起始位置在整个过程中不断右移,而且每次沿后缀指针上溯都会导致该位置严格右移。

    由于在程序结束时这一起始位置不超过n,所以这一过程的时间复杂度是线性的。

     (虽然没什么用,但同样的讨论可以被用来证明第一处的线性性,以代替对状态个数线性性的证明。)

     

    算法的实现

    首先我们描述一个数据结构,它储存特定的一段信息(len,link,转移列表)。如有必要,你可以增加表示终止状态的标签,以及其他需要

    的信息。

    我们用STL容器map存储转移列表,其空间复杂度为O(n),而处理整个字符串的时间复杂度为O(n*logk)。

     

    struct state {
    	int len,link;
    	map<char,int> next;
    };
    

     

     

    后缀自动机本身将被储存在一个state类型的数组中。正如下一节中将证明的那样,如果程序中所处理字符串的最大可能长度是MAXN,

    那么至多会占用2*MAXN-1个状态。同时,我们储存变量last——当前匹配整个字符串的状态。

     

    const int MAXLEN = 100000;
    state st[MAXLEN*2];
    int sz, last;
    

     

    我们给出初始化后缀自动机的函数(新建一个初始状态):

     

    void sa_init() {
       sz = last = 0;
       st[0].len = 0;
       st[0].link = -1;
       ++sz;
    	/*
    	// 若关于不同的字符串多次建立后缀自动机,就需要执行这些代码:
    	for (int i=0; i<MAXLEN*2; ++i)
    		st[i].next.clear();
    	*/
    }
    

     

     

     

     

     

    最后,我们给出基础函数的实现——向当前字符串的尾部添加一个字符,并相应地修改后缀自动机:

     

    void sa_extend (char c) {
    	int cur = sz++;
    	st[cur].len = st[last].len + 1;
    	int p;
    	for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
    		st[p].next[c] = cur;
    	if (p == -1)
    		st[cur].link = 0;
    	else {
    		int q = st[p].next[c];
    		if (st[p].len + 1 == st[q].len)
    		st[cur].link = q;
    		else {
    		int clone = sz++;
    			st[clone].len = st[p].len + 1;
    			st[clone].next = st[q].next;
    			st[clone].link = st[q].link;
    			for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
    			st[p].next[c] = clone;
    			st[q].link = st[cur].link = clone;
    		}
    	}
    	last = cur;
    }
    

     

     

     

     

     

    像前面提到的那样,如果牺牲部分空间(空间复杂度增至O(nk),其中k是字母表大小),就能够对任何k实现O(n)构建自动机——但这将

    会在每个状态中建立一个长度为k的数组(用于快速按字符查询转移)和一个转移链表(用于快速遍历或者复制所有转移)。

     

    后缀自动机的其他性质

     

    状态的数量

    由长度为n的字符串s建立的后缀自动机的状态个数不超过2n-1(对于n>=3)。

    上面描述的算法证明了这一性质(最初自动机包含一个初始节点,第一步和第二步都会添加一个状态,余下的n-2步每步至多由于需要分割,增加两个状态)。

    不过,即使不涉及算法,这一性质也容易证明。注意到状态个数等于不同的终点集合的个数。此外,终点集合按“子女是父节点的不同子集”这一原则构成一棵树。

    考虑这棵树,将其稍作扩充:若一个内部节点只有一个儿子,那就意味着该儿子的终点集合不包含其父亲终点集合中的至少一个值;那么我们就创建一个虚拟节点,

    其终点集合为这个值。最终,我们得到了一棵树,其内部节点度数均>1,而叶子节点个数不超过n。因此,这棵树的结点个数不超过2n-1.自然,原树的结点个数也

    不超过2n-1.

    这样我们就独立于算法地证明了这一性质。

    有趣的是,这一上限无法被改善,即存在达到这一上限的例子: 

    "abbbb..."

    从第三次开始,每次添加字符时都会进行分割,因此结点个数将达到2n-1.

     

    转移的数量

    由长度为n的字符串s建立的后缀自动机中,转移的数量不超过3n-4(对于n>=3)。

     

    证明.

     我们计算“连续的”转移个数。考虑以t_0为初始节点的自动机的最长路径树。这棵树将包含所有连续的转移,树的边数比结点个数小1,这意

    味着连续的转移个数不超过2n-2.

      我们再来计算不连续的转移个数。考虑每个不连续转移;假设该转移——转移(p,q),标记为c。对自动机运行一个合适的字符串u+c+w,其

    中字符串u表示从初始状态到p经过的最长路径,w表示从q到任意终止节点经过的最长路径。一方面,对所有不连续转移,字符串u+c+w都是不同

    的(因为字符串u和w仅包含连续转移)。另一方面,每个这样的字符串u+c+w,由于在终止状态结束,它必然是完整串s的一个后缀。由于s的非

    空后缀仅有n个,并且完整串s不能是某个u+c+w(因为完整串s匹配一条包含n个连续转移的路径),那么不连续转移的总共个数不超过n-1.

      将这两个限制加起来,我们就得到了总数限制3n-3.注意到虽然状态个数限制可以被数据"abbbb..."达到,但这个数据并未达到3n-3的转移个数

    上限。它的转移个数是3n-4,符合要求。

      有趣的是,仍然存在达到转移个数上限的数据:

    "abbb...bbbc"

    与后缀树的联系,在后缀自动机上建立后缀树及反之

      我们证明两个定理,它们能说明后缀树和后缀自动机之间的相互关系。

    首先我们假定输入字符串的每个后缀都在其后缀树中对应一个节点(对于任意字符串而言并不一定成立:例如,对于字符串 "aaa...")。在后缀

    树的典型实现中,我们通过在字符串的末尾加上一个特殊符号(例如"#"或"$")来保证这一点。

      方便起见,我们引入如下记号:rev(s)——将字符串s反过来写,DAWG(s)——这是由字符串s建立的后缀自动机,ST(s)——这是s的后缀树。

      我们介绍“扩展指针”的概念:对于树节点v和字符c,ext[c,v]指向树中对应于字符串c+v的节点(如果路径c+v在某边的终点结束,那就将其指向该

    边的较低点);如果这样一条路径c+v不在树中,那么扩展指针未定义。在某种意义上,扩展指针的对立面就是后缀链接。

     

    定理1.DAWG(s)中后缀链接组成的树就是后缀树ST(rev(s))

     

    定理2.图DAWG(s)的边都能用后缀树ST(rev(s))的扩展指针表示。另外,DAWG(s)中的连续转移就是ST(rev(s))中反向的后缀指针。

     

    这两条定理允许使用两个数据结构之一在O(n)的时间内构建另外一个——这两个简单的算法将在下面定理3,4讨论。

      出于说明需要,我们下面展示一个包含后缀链接的后缀自动机的例子,以及其倒序字符串的相应后缀树。例如,令字符

    串s="abcbc"。

      DAWG("abcbc")(出于简便我们在每个状态上标出其识别的最长串):


     

     

    ST("cbcba")

     

     

     

    引理.

    对任意两个子串u和w,如下三个陈述是等价的:

    ·        在字符串s中endpos(u)=endpos(w)

    ·        在字符串rev(s)中firstpos(rev(u))=firstpos(rev(w))

    ·        在后缀树ST(rev(s))中,rev(u)和rev(w)匹配从根开始的一段相同路径。

     

    证明十分显然:如果两个字符串的起始位置集合相同,那么一个字符串只作为另外一个的前缀出现,这意味着在后缀树中,二者之

    间并没有其他节点。

     因此,后缀自动机中的状态和后缀树中的节点一一对应。

     

    定理1的证明.

     后缀自动机中的状态和后缀树中的节点一一对应.

     

    考虑任意后缀链接y=link(x)。根据后缀链接的定义,longest(y)是longest(x)的一个后缀,并且y是所有满足条件(和x的终点集合不同)

    的状态中使len(y)最大者。

     在rev(s)中,这意味着link(x)指向x所对应字符串的最长前缀,该前缀对应一个不同的状态y。换句话说,后缀链接link(x)指向后缀树中节

    点x的父亲。

     

    定理2的证明.

     

    后缀自动机中的状态和后缀树中的节点一一对应。

     

    考虑后缀自动机DAWG(s)中的任意转移(x,y,c)。这意味着y是包含子串longest(x)+c的终点集合等价类。对于rev(s),y对应了一个子串,

    该子串的firstpos(在文本rev(s)中)和c+rev(longest(x))的firstpos相同。

     这意味着:

    rev(longest(y))=ext[c,rev(longest(x))].

    (注:这里的用法并不严谨……请自行把字符串和节点对应) 

    也就是该定理的第一部分,我们还需要证明第二部分:自动机中的所有连续转移对应树中的后缀指针。对于连续转移,有length(y)=length(x)+1,

    即在标识字符c后我们到达了一个状态,它是一个不同的等价类。这意味着在rev(s)的后缀树中,x节点对应的字符串恰好是y节点所对应字符串的,长

    度比它小1的后缀——也就是说,后缀树中y的后缀指针指向x,(x,y)就是树中的反向后缀指针。

     

    定理得证。

     

    定理3.

    使用后缀自动机DAWG(s),我们可以用O(n)的时间构建后缀树ST(rev(s))。

     

    定理4.

    使用后缀树ST(rev(s)),我们可以用O(n)的时间构建后缀自动机DAWG(s)。

     

    定理3的证明.

    后缀树ST(rev(s))的节点和DAWG(s)中的状态一一对应。树中与自动机中状态v相对应的节点表示一个长度为len(v)的字符串。

     

    根据定理1,ST(rev(s))中的边恰好是把DAWG(s)的后缀链接反向,而边的标记可以借助不同状态的len计算(译者注:从叶子开始,利用自动

    机中状态的len值计算后缀树中的节点对应于哪个子串),或者更方便地,对自动机中每个状态我们都能知道其endpos集合中的一个元素(在构建

    后缀自动机时维护)。

     至于树中的后缀指针,我们可以基于定理2构建:查找自动机中所有的连续转移,对所有这样的转移(x,y)我们都在树中添加一个后缀指针link[y]=x。

     因此,在O(n)时间内我们就可以构建一棵后缀树及其中的后缀指针。

     (如果我们认为字母表的大小k并非常数,那么重建操作将花费O(n*logk)的时间。)

     

    定理4的证明.

    后缀自动机DAWG(s)包含的状态和ST(rev(s))中的节点一一对应。对每个状态v,其对应的最长字符串longest(v)都和后缀树中从根到v的路径翻转后

    形成的字符串相同。

     

    根据定理2,为了构建自动机中的所有转移,我们需要找到所有扩展ext[c,v]的指针。

     首先,注意到其中的一些指针直接由树中的后缀指针得到。事实上,如果对于树中任意节点x,我们考虑其后缀指针y=link[x],那就意味着自动机中

    有一个从y指向x的连续转移,标记为树节点x所对应字符串的第一个字符。

     不过,只是这样我们并不能找到所有的扩展。额外地,有必要从叶子到根遍历后缀树,而且对于每个节点v都遍历其所有儿子,对每个儿子观察所有

    扩展指针ext[c,w],如果该指针上的字符c在节点v中还未发现,就将其复制到v中:

    ext[c,v]=ext[c,w],如果ext[c,w]=nil.

    这一过程将在O(n)时间内完成,如果我们认为字母表的大小是常数。

    最终,还需要建立后缀自动机中的后缀链接。而根据定理1,后缀链接可以直接由后缀树ST(rev(s))的边获得。

    这样,我们就得到使用从倒序字符串的后缀树建立后缀指针的O(n)算法。

     (不过,若字母表的大小k是变量,那么渐进复杂度就是O(n*logk))。

     

    在解决问题中的应用

    下面看在后缀自动机的帮助下我们能做什么。

     

    简便起见,我们假设字母表的大小k为常数。

     

    存在性查询

     

    问题.给定文本T,询问格式如下:给定字符串P,问P是否是T的子串。 

    复杂度要求.预处理O(length(T)),每次询问O(P)。

     

    算法.我们对文本T用O(length(T))建立后缀自动机。

    现在回答单次询问。假设状态——变量v,最初是初始状态T_0.我们沿字符串P给出的路径走,因此从当前状态经转移来到新的状态v

    。如果在某时刻,当前状态没有要求字符的转移,那么答案就是"no"。如果我们处理了整个字符串P,答案就是"yes"。

    显然这一算法将在时间O(length(P))内运行完毕。并且,该算法实际上找出了P在文本中出现过的最长前缀——如果模式串使得这些前缀

    都很短,算法将比处理全部模式串要快得多。

     

    不同的子串个数

     

    问题.给定字符串S,问它有多少不同的子串。

     复杂度要求.O(length(S))。

     

    算法.我们将字符串S建立后缀自动机。

     在后缀自动机中,S的任意子串都对应自动机中的一条路径。答案就是从初始节点t_0开始,自动机中不同的路径条数。

     已知后缀自动机是一张有向无环图,我们可以考虑用动态规划计算不同的路径数量。

      也就是,令d[v]为从状态v开始的不同路径条数(包括长度为零的路径),则有转移:


     

     

     

     

     

    即d[v]是v所有后继节点的d值之和加上1.

    最终答案就是d[t_0]-1(减一以忽略空串)。

     

    不同子串的总长

     

    问题.给定字符串S,求其所有不同子串的总长度。

    复杂度要求.O(length(S)).

     

    算法.这一问题的答案和上一题类似,但现在我们必须考虑两个状态:不同子串的个数d[v]和它们的总长ans[v].

      上一题已描述了d[v]的计算方法,而ans[v]的计算方法如下:

     

    即取所有后继节点w的ans值,并将它和d[w]相加。因为这是每个字符串的首字母。

     

    字典序第k小子串

     

    问题.给定字符串S,一系列询问——给出整数K_i,计算S的所有子串排序后的第K_i个。

    复杂度要求.单次询问O(length(ans)*Alphabet),其中ans是该询问的答案,Alphabet是字母表大小。

     

     算法.这一问题的基础思路和上两题类似。字典序第k小子串——自动机中字典序第k小的路径。因此,考虑从每个状态出

    发的不同路径数,我们将得以轻松地确定第k小路径,从初始状态开始逐位确定答案。

     

    最小循环移位

     

    问题.给定字符串S,找到和它循环同构的字典序最小字符串。

     复杂度要求.O(length(S)).

     

    算法.我们将字符串S+S建立后缀自动机。该自动机将包含和S循环同构的所有字符串。

     从而,问题就简化成了在自动机中找出字典序最小的,长度为length(S)的路径,这很简单:从初始状态开始,每一步都贪心地走

    ,经过最小的转移。

     

    出现次数查询

     

    问题.给定文本T,询问格式如下:给定字符串P,希望找出P作为子串在文本T中出现了多少次(出现区间可以相交)。

     复杂度要求.预处理O(length(T)),单次询问O(length(P)).

     

    算法.我们将文本T建立后缀自动机。

     然后我们需要进行预处理:对自动机中的每个状态v都计算cnt[v],等于其endpos(v)集合的大小。事实上,所有在T中对应同一状态的

    字符串都在T中出现了相同次数,该次数等于endpos中的位置数。

     不过,我们无法对所有状态明确记录endpos集合,所以我们只计算其大小cnt.

     为了实现这一点,如下处理。对每个状态,如果它不是由“拷贝”而来,最初就赋值cnt=1.然后我们按长度len降序遍历所有序列,并将

    当前的cnt[v]加给后缀链接:

     cnt[link(v)]+=cnt[v].

      你可能会说我们并没有对每个状态计算出了正确的cnt值。

     为什么这是对的?不经“拷贝”而来的状态恰好有length(S)个,而且其中的第i个是我们添加第i个字符时得到的。因此,最初这些状态的cnt=1,

    其他状态的cnt=0.

     然后我们对每个状态v执行如下操作:cnt[link(v)]+=cnt[v].其意义在于,如果某字符串对应状态v,曾在cnt[v]中出现过,那么它的所有后缀都

    同样在其中出现。

     这样,我们就掌握了如何对自动机中所有状态计算cnt值的方法。

     在此之后,询问的答案就变得平凡——只需要返回cnt[t],其中t是模式串P所对应的状态。

     

    首次出现位置查询

     

    问题.给定文本T,询问格式如下:给定字符串P,求P在文本中第一次出现的位置。

     复杂度要求.预处理O(length(T)),单次询问O(length(P)).

     

    算法.对文本T建立后缀自动机。

     为了解决这一问题,我们需要预处理firstpos,找到自动机中所有状态的出现位置,即,对每个状态v我们希望找到一个位置firstpos[v],代表

    其第一次出现的位置。换句话说,我们希望预先找出每个endpos(v)中的最小元素(我们无法明确记录整个endpos集合)。

      维护这些firstpos的最简单方法是在构建自动机时一并计算,当我们创建新的状态cur时,一旦进入函数sa_extend(),就确定该值:

     firstpos(cur)=len(cur)-1(如果我们的下标从0开始)。

    当拷贝节点q时,令:

     firstpos(clone)=firstpos(q),(因为只有一个别的可能值——firstpos(cur),显然更大)。

     这样就得到了查询的答案——firstpos(t)-length(P)+1,其中t是模式串P对应的状态。

     

    所有出现位置查询

     

    问题.给定文本T,询问格式如下:给定字符串P,要求给出P在T中的所有出现位置(出现区间可以相交)。

    复杂度要求.预处理O(length(T))。单次询问O(length(P)+answer(P)),其中answer(P)是答案集合的大小,即,要求时间复杂度和输入输出同阶。

     

    算法.对文本T建立后缀自动机,和上一个问题相似,在构建自动机的过程中对每个状态计算第一次出现的终点firstpos。

     

    假设我们收到了一个询问——字符串P。我们找到了它对应的状态t。

     显然应当返回firstpos(t)。还有哪些位置?我们考虑自动机中那些包含了字符串P的状态,即那些P是其后缀的状态。

     换言之,我们需要找出所有能通过后缀链接到达状态t的状态。

     因此,为了解决这一问题,我们需要对每个节点储存指向它的所有后缀链接。为了找到答案,我们需要沿着这些翻转的后缀链接进行DFS/BFS,从状

    态t开始。

     这一遍历将在O(answer(P))时间内结束,因为我们不会访问同一状态两次(因为每个状态的后缀链接仅指向一个点,因此不可能有两条路径通往同一

    状态)。

     然而,两个状态的firstpos值可能会相同,如果一个状态是由另一个拷贝而来。但这不会影响渐进复杂度,因为每个非拷贝得到的节点只会有一个拷贝。

     此外,你可以轻松地除去那些重复的位置,如果我们不考虑那些拷贝得来的状态的firstpos。事实上,所有拷贝得来的状态都被其“母本”状态的后缀链接

    指向。因此,我们对每个节点记录标签is_clon,我们不考虑那些is_clon=true的状态的firstpos。这样我们就得到了answer(P)个不重复地状态。

     给出一个离线版本的实现:

     

    struct state {
    	...
    	bool is_clon;
    	int first_pos;
    	vector<int> inv_link;
    	};
    	
    	 
    ... 后缀自动机构建完毕 ...
    for (int v=1; v<sz; ++v)
    	st[st[v].link].inv_link.push_back (v);
    ...
      
     
    // 回答询问--返回所有的出现位置(出现区间可能有重叠)
    void output_all_occurences (int v, int P_length) {
       if (! st[v].is_clon)
    		cout << st[v].first_pos - P_length + 1 << endl;
       for (size_t i=0; i<st[v].inv_link.size(); ++i)
    		output_all_occurences (st[v].inv_link[i], P_length);
    }
    

     

     

     

    查询不在文本中出现的最短字符串

    问题.给定字符串S和字母表。要求找出一个长度最短的字符串,使得它不是S的子串。

    复杂度要求.O(length(S)).

     

     算法.在字符串S的后缀自动机上进行动态规划。

     令d[v]为节点v的答案,即,我们已经输入了字符串的一部分,匹配到v,我们希望找出有待添加的最少字符数量,以到达一个不存在的转移。

     计算d[v]非常简单。如果在v处某个转移不存在,那么d[v]=1:用这个字符来“跳出”自动机,以得到所求字符串。

     否则,一个字符串无法达到要求,因此我们必须取所有字符中的最小答案:

     

    原问题的答案等于d[t_0],而所求字符串可以用记录转移路径的方法得到。

     

    求两个字符串的最长公共子串

     

    问题.给定两个字符串S和T。要求找出它们的最长公共子串,即一个字符串X,它同时是S和T的子串。

      复杂度要求.O(length(S)+length(T)).

     

    算法.我们对字符串S建立后缀自动机。

     

    我们按照字符串T在自动机上走,查找它每个前缀在S中出现过的最长后缀。换句话说,对字符串T中的每个位置,我们都想找出S和T在该位置结束的最长公共子串。

     

    为了实现这一点,我们定义两个变量:当前状态v和当前长度l。这两个变量描述了当前的匹配部分:其长度和状态,对应哪个字符串(如果不储存长度就无法确定这一点,因为一个状态可能匹配多个有不同长度的字符串)。

     

    最初,p=t_0,l=0,即,匹配部分为空。

     

    现在我们考虑字符T[i],我们希望找到这个位置的答案。

    ·        如果自动机中的状态v有一个符号T[i]的转移,我们可以简单地走这个转移,然后将长度l加一。

    ·        如果状态v没有该转移,我们应当尝试缩短当前匹配部分,为此应当沿着后缀链接走:
    v=link(v).
    在此情况下,当前匹配长度必须被减少,但留下的部分尽可能多。显然,应令l=len(v):
    l=len(v).
    若新到达的状态仍然没有我们想要的转移,那我们必须再次沿着后缀链接走,并且减少l的值,直到我们找到一个转移(那就返回第一步),或者我们最终到达了空状态-1(这意味着字符T[i]并未在S中出现,所以令v=l=0然后继续处理下一个i)。

    原问题的答案就是l曾经达到的最大值。

     

    这种遍历方法的渐进复杂度是O(length(T)),因为在一次移动中我们要么将l加一,要么沿着后缀链接走了若干次,每次都会严格减少l。因此,l总共的减少值之和不可能超过length(T),这意味着线性时间复杂度。

     

    代码实现:

     

    string lcs (string s, string t) {
    	sa_init();
    	for (int i=0; i<(int)s.length(); ++i)
    		sa_extend (s[i]);
    	
    	int v = 0,  l = 0,
    		best = 0,  bestpos = 0;
    	for (int i=0; i<(int)t.length(); ++i) {
    		while (v && ! st[v].next.count(t[i])) {
    			v = st[v].link;
    			l = st[v].length;
    		}
    		if (st[v].next.count(t[i])) {
    		v = st[v].next[t[i]];
    		 ++l;
    		}
    		if (l > best)
    			best = l,  bestpos = i;
    	}
    	return t.substr (bestpos-best+1, best);
    }
    

     

     

    多个字符串的最长公共子串

     

    问题.给出K个字符串S_1~S_K。要求找出它们的最长公共子串,即一个字符串X,它是所有S_i的子串。

      复杂度要求.O(∑length(S_I)*K).

     

    算法.将所有S_i连接在一起成为一个新的字符串T,其中每个S_i后要加上一个不同的分隔符D_i(即加上K个额外的不同特殊字符D_1~D_K):

     

    我们对字符串T构建后缀自动机。

     现在我们需要在后缀自动机找出一个字符串,它是所有字符串S_i的子串。注意到如果一个子串在某个字符串S_j中出现过,那么后缀自动机中存在一

    条以这个子串为前缀的路径,包含分隔符D_j,但不包含其他分隔符D_1,...,D_j-1,D_j+1,...,D_k。

     因此,我们需要计算“可达性”:对自动机中的每个状态和每个字符D_i,计算是否有一条从该状态开始的路径,包含分隔符D_i,但不包含别的分隔符。

    很容易用DFS/BFS或者动态规划实现。在此之后,原问题的答案就是字符串longest(v),其中v能够到达所有的分隔符。

     

    OJ上的题目

    可以用后缀自动机解决的题目:

    SPOJ#7258 SUBLEX"Lexicographical Substring Search"

    BZOJ#2555 Substring

    SPOJ#8222 NSUBSTR"Substrings"

    SPOJ#1812 LCS2"Longest Common Substrings II"

    BZOJ#3998 弦论

     

    参考文献

    我们首先给出和后缀自动机有关的一些第一手研究:

    ·        A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, R.McConnell.Linear Size Finite Automata for the Set of All Subwordsof a Word. An Outline of Results [1983]

    ·        A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler.The SmallestAutomaton Recognizing the Subwords of a Text[1984]

    ·        Maxime Crochemore. OptimalFactor Transducers [1985]

    ·        Maxime Crochemore. Transducersand Repetitions [1986]

    ·        A. Nerode. Linear automatontransformations [1958]

    此外,还有一些当代资源,这一主题在许多有关字符串算法的书籍中被提到:

    ·        Maxime Crochemore, Wowjcieh Rytter. Jewels ofStringology [2002]

    ·        Bill Smyth. Computing Patterns in Strings [2003]

    ·        Билл Смит. Методы и алгоритмы вычислений на строках [2006]

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 后缀自动机的详解

    2018-10-25 12:04:13
    关于后缀自动机的一系列讲解,包括(概念,原理,证明,代码,例题......)。
  • ac自动机是一种基于trie树的算法,其本质和kmp上的处理很相似。 trie树结构:https://blog.csdn.net/qq_38890926/article/details/81158021 kmp转移思路:...

    ac自动机是一种基于trie树的算法,其本质和kmp上的处理很相似。

    trie树结构:https://blog.csdn.net/qq_38890926/article/details/81158021

    kmp转移思路:https://blog.csdn.net/qq_38890926/article/details/81158132

     

    ac自动机组要由三个部分组成:trie树的建立  fail指针的匹配  对ac自动机的询问

    每次建立自动机会有一次初始化

    ac自动机类

    struct node    //node结构体
    {
        int exist;
        node* next[26],fail;
        node()   //初始化
        {
            exist=0;
            fail=NULL;
            memset(next,0,sizeof(next));
        }
    };
    struct AC
    {
        node *root;
        const int SIZE=26;
        AC(){root=newnode();}
        void init(){del(root);root=newnode();} //时间换空间
        //void init(){root=newnode();}      //空间换时间
        node* newnode(){return new node;}
        //int idx(char c){return c;}     //size=128,可见字符在128以内
        inline int idx(char c){return c-'a';}     //size=26
    
        void insert(char *s,int num)  //插入字符串建树
        {
            node *u=root;
            int len=strlen(s);
            for(int i=0;i<len;i++)
            {
                int c=idx(s[i]);
                if(u->next[c]==NULL)u->next[c]=new node();
                u=u->next[c];
            }
            u->exist=num;
            /*其他操作,在每次插入字符串的结尾node上进行操作*/
        }
    
        queue<node*> q; //fail指针的构建,采用bfs
        void build()
        {
            while(!q.empty())q.pop();q.push(root);
            while(!q.empty())
            {
                node* u=q.front();q.pop();//u也有u指向fail位置的性质,fail形成的集合结点有相同性质
                for(int i=0;i<SIZE;i++)
                {
                    if(u->next[i]!=NULL)  //新结点,先构建fail,再加入队列
                    {
                        if(u==root)u->next[i]->fail=root;//判断当前是否是根,指向根
                        else
                        {             //不是根节点往回遍历,处理和kmp相似
                            node *f=u->fail;
                            while(f!=root && f->next[i]==NULL)f=f->fail;
                            if(f->next[i]!=NULL)f=f->next[i];
                            u->next[i]->fail=f;
                        }
                         q.push(u->next[i]);
                    }
                }
            }
        }
    
        void query(char* s)
        {
            node *u=root;
            int len=strlen(s);
            for(int i=0;i<len;i++)   //将s字符串一直向下匹配
            {
                int c=idx(s[i]);
                while(u!=root && u->next[c]==NULL)u=u->fail;
                if(u->next[c]!=NULL)
                {
                    u=u->next[c];
                    node* temp=u;
                    while(temp!=NULL)
                    {
                        if(temp->exist)
                        {
                            vec[tot]=temp->exist;
                            tot++;
                        }
                        temp=temp->fail;
                    }
                }
            }
        }
        void del(node* rt)
        {
            if(rt==NULL)return;
            for(int i=0;i<SIZE;i++)if(rt->next[i]!=NULL)del(rt->next[i]);
            delete rt;
        }
    };
    AC ac;

    数组实现

    struct node    //node结构体
    {
        bool exist;
        int next[55];
        int fail;
        node()   //初始化
        {
            exist=0;
            fail=0;
            memset(next,0,sizeof(next));
        }
    };
    
    struct AC
    {
        int tot;
        node trie[505];
        AC(){tot=1;memset(trie,0,sizeof(trie));}
        void init(){tot=1;memset(trie,0,sizeof(trie));}
        inline int idx(char c){return mc[c];}     //size=26
    
        void insert(char *s)  //插入字符串建树
        {
            int u=1;
            int len=strlen(s);
            for(int i=0;i<len;i++)
            {
                int c=idx(s[i]);
                if(trie[u].next[c]==0)trie[u].next[c]=++tot;
                u=trie[u].next[c];
            }
            trie[u].exist=true;
        }
    
        queue<int> q; //fail指针的构建,采用bfs的方式
        void build()
        {
            while(!q.empty())q.pop();
            q.push(1);
            while(!q.empty())
            {
                int u=q.front();q.pop();//u指向fail位置具有的性质u也有,即fail形成的集合结点有相同性质!!
                for(int i=0;i<SIZE;i++)
                {
                    int v=trie[u].next[i];
                    if(v!=0)  //对于每次存在的新结点,先构建fail,再加入队列
                    {
                        if(u==1)trie[v].fail=1;  //判断当前是否是根结点,是的话下面的指向根
                        else
                        {                        //不是根节点的情况往回遍历,以下处理和kmp相似
                            int f=trie[u].fail;
                            while(f!=1 && trie[trie[f].next[i]].fail==0)f=trie[f].fail;
                            if(trie[f].next[i]!=1)f=trie[f].next[i];
                            trie[v].fail=f;
                        }
                        q.push(v);
                    }
                }
            }
        }
    };
    AC ac;
    struct node    //node结构体
    {
        bool exist;
        int next[26],fail;
        node()   //初始化
        {
            exist=0;
            fail=0;
            memset(next,0,sizeof(next));
        }
    };
    struct AC
    {
        int tot;
        node trie[505];
        AC(){init();}
        void init(){tot=1;memset(trie,0,sizeof(trie));}
        inline int idx(char c){return mp[c];} //size=26
    
        void insert(char *s)  //插入字符串建树
        {
            int u=0;
            int len=strlen(s);
            for(int i=0;i<len;i++)
            {
                int c=idx(s[i]);
                if(trie[u].next[c]==0)trie[u].next[c]=tot++;
                u=trie[u].next[c];
            }
            trie[u].exist=true;
        }
    
        queue<int> q; //bfs构建fail指针
        void build()
        {
            while(!q.empty())q.pop();
            for(int i=0;i<26;i++) //先处理根
            {
                int v=trie[0].next[i];
                if(v==0)continue;
                trie[v].fail=0;
                q.push(v);
            }
            while(!q.empty())
            {
                int u=q.front();q.pop();//u指向fail位置具有的性质u也有!
                for(int i=0;i<26;i++)
                {
                    int v=trie[u].next[i];
                    if(v)
                    {
                        trie[v].fail=trie[trie[u].fail].next[i];
                        q.push(v);
                    }
                    else trie[u].next[i]=trie[trie[u].fail].next[i];//就是fail
                }
            }
        }
        void query(char *s)
        {
    
        }
    };
    AC ac;

    后缀自动机

     

     

    应用

    1.dp

    在ac自动机上面进行dp,需要注意的事情:

    1.由于构建fail的时候,下层的结点具有与其fail结点共有的性质,我们需要将fail节点的性质向下赋值。

    2.dp的思想:将自动机上面的所有结点当作一种状态,记录处于当前状态的dp值,接下来可以进行字符串的转移,利用fail指针进行的转移来进行相关的dp。

    #include<iostream>
    #include<cstdio>
    #include<queue>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<cstdlib>
    #include<cmath>
    #include<set>
    #include<map>
    #include<stack>
    #include<iomanip>
    #include<cstring>
    #include<sstream>
    #include<iomanip>
    #include<fstream>
    #include<fstream>
    
    #define maxn 1005
    #define maxm 105
    typedef long long ll;
    const int inf=1e8+7;
    ll mod=998244353;
    const double eps=1e-9;
    using namespace std;
    
    
    inline void read(int &x){scanf("%d",&x);}
    inline void readll(ll &x){scanf("%lld",&x);}
    
    int n;
    map<char,int> mp;
    char s[maxn];
    ll f[maxn][maxn];
    
    int SIZE=4;
    struct node    //node结构体
    {
        bool exist;
        int next[4],fail;
        node()   //初始化
        {
            exist=0;
            fail=0;
            memset(next,0,sizeof(next));
        }
    };
    struct AC
    {
        int tot;
        node trie[1005];
        AC(){init();}
        void init(){tot=1;memset(trie,0,sizeof(trie));}
        inline int idx(char c){return mp[c];} //size=26
    
        void insert(char *s)  //插入字符串建树
        {
            int u=0,len=strlen(s);
            for(int i=0;i<len;i++)
            {
                int c=idx(s[i]);
                if(trie[u].next[c]==0)trie[u].next[c]=tot++;
                u=trie[u].next[c];
            }
            trie[u].exist=true;
        }
        queue<int> q; //bfs构建fail指针
        void build()
        {
            while(!q.empty())q.pop();
            for(int i=0;i<SIZE;i++) //先处理根
            {
                int v=trie[0].next[i];
                if(v==0)continue;
                trie[v].fail=0;
                q.push(v);
            }
            while(!q.empty())
            {
                int u=q.front();q.pop();
                if(trie[trie[u].fail].exist==true)trie[u].exist=true;//u的fail的性质u也有
                for(int i=0;i<SIZE;i++)
                {
                    int v=trie[u].next[i];
                    if(v)
                    {
                        trie[v].fail=trie[trie[u].fail].next[i];
                        q.push(v);
                    }
                    else trie[u].next[i]=trie[trie[u].fail].next[i];//就是fail
                }
            }
        }
        ll query(char *str)
        {
            ll res=inf;
            int len=strlen(str);
            for(int i=0;i<=len;i++)
                for(int j=0;j<tot;j++)
                    f[i][j]=inf;
            f[0][0]=0;
            for(int i=1;i<=len;i++)
            {
                for(int j=0;j<tot;j++)
                {
                    for(int k=0;k<4;k++)
                    {
                        int v=trie[j].next[k];
                        if(trie[v].exist==0)
                        {
                            if(mp[str[i-1]]==k)f[i][v]=min(f[i][v],f[i-1][j]);
                            else f[i][v]=min(f[i][v],f[i-1][j]+1);
                        }
                    }
                }
            }
            for(int i=0;i<tot;i++)res=min(res,f[len][i]);
            if(res==inf)res=-1;
            return res;
        }
    };
    AC ac;
    
    
    int main()
    {
        mp['A'] = 0;mp['C'] = 1;mp['G'] = 2;mp['T'] = 3;
        int cas=0;
        while(scanf("%d",&n)&& n)
        {
            ac.init();
            for(int i=0;i<n;i++)
            {
                scanf("%s",s);
                ac.insert(s);
            }
            ac.build();
            scanf("%s",s);
            printf("Case %d: %lld\n",++cas,ac.query(s));
        }
        return 0;
    }
    

     

    展开全文
  • 思路来源 ... ... 前置知识 自动机的知识(编译原理那一套,比如有限状态自动机云云,知道能在其上...AC自动机、Trie树、后缀数组 死记硬背环节 证明和心得(后附)感觉用处不大,直接计入死记硬背和抄板子做题环节 ...

    思路来源

    https://www.luogu.com.cn/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie 首推这一篇

    https://www.cnblogs.com/zjp-shadow/p/9218214.html 也看了这一篇,也不错

    http://hihocoder.com/problemset/problem/1441 hihocoder板子题

    https://www.luogu.com.cn/problem/solution/P3804 洛谷板子题

    前置知识

    自动机的知识(编译原理那一套,比如有限状态自动机云云,知道能在其上沿边转移感觉就可)

    AC自动机、Trie树、后缀数组

     

    死记硬背环节

    证明和心得(后附)感觉用处不大,直接计入死记硬背和抄板子做题环节

    后缀自动机(SAM),是一个最小的确定有限状态自动机(DFA),接受且只接受S的后缀

    parent树和自动机节点共用,时间复杂度O(n),空间复杂度O(n)

     

    parent(也称fa,后缀链接link):当一个节点的串,在变为其后缀,且endpos发生了扩大时,最长的那个后缀对应的节点

    endpos(也称right):每个节点对应的串的endpos集合是一致的,每个子串唯一出现在某个节点里

    len:一个节点内代表的串的最大长度

    minlen:一个节点内代表的串的最小长度,由于a回跳到父亲fa(a)的时候len(fa)+1=minlen(a),故一般不存

    ch[0-26](后缀转移transfer):自动机上对应字母的转移

     

    配合两张图食用,便于记忆这些概念

    图1:abcd的后缀自动机,

    红色括号是endpos集合,字母是自动机转移

    图二:aaba的后缀自动机,

    红色数字是节点对应的最长子串的长度len,蓝边是其parent树上的父亲fa

    板子

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    struct NODE
    {
        int ch[26];
        int len,fa;
        NODE(){memset(ch,0,sizeof(ch));len=0;}
    }dian[N<<1];
    int las=1,tot=1;
    void add(int c)
    {
        int p=las;int np=las=++tot;
        dian[np].len=dian[p].len+1;
        for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np;
        if(!p)dian[np].fa=1;//以上为case 1
        else
        {
            int q=dian[p].ch[c];
            if(dian[q].len==dian[p].len+1)dian[np].fa=q;//以上为case 2
            else
            {
                int nq=++tot;dian[nq]=dian[q];
                dian[nq].len=dian[p].len+1;
                dian[q].fa=dian[np].fa=nq; 
                for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq;//以上为case 3
            }
        }
    }
    char s[N];int len;
    int main()
    {
        scanf("%s",s);len=strlen(s);
        for(int i=0;i<len;i++)add(s[i]-'a');
    }

    性质

    ①endpos:一个子串在原串中所有出现的地方,其末位置下标的集合

    如串abcab,endpos(ab)={2,5}

     

    ②endpos相同,一个必为另一个后缀,

    考虑abcdbcd,当abcd变成后缀bcd的时候,endpos增加,bcd变成cd的时候,endpos不变

     

    ③根据②,任意两个子串的endpos集合,要么一个是另一个子集,要么二者相交为空,

    只要有一个相交的位置,说明是后缀,后缀就是含于的情况

     

    ④根据②,在子串缩短为其后缀的过程中,要么endpos不变,要么增加,把endpos相同的视为一个等价类节点

    在SAM中,一个子串只属于一个节点,这个节点内的子串的endpos都相同

     

    ⑤endpos等价类(节点)个数为O(n),

    这个没看懂曾经看懂过,可以参考原博客

     

    ⑥parent树、自动机

    后缀自动机的parent树和自动机的节点是共用的,

    parent树往祖先跳的时候,endpos会变大,实际上是当前串变为其后缀串,在节点中用fa定义

    自动机就是读进这个字符转移到哪个点,定义了一种转移关系,在节点中用ch[0-26]定义,类似trie

     

    ⑦由②,不难发现,endpos不变的一段子串是连续的,

    分别记minlen和len为这个点对应的子串的最小长度和最大长度

    记点a覆盖的串的长度为[minlen(a),len(a)],则从minlen(a)再缩短一个长度的时候,endpos扩充,跳到父亲

    所以有len(fa(a))+1=minlen(a),fa(a)是a在parent树上的父亲

     

    ⑧后缀自动机的边数为O(n)

    这个没看懂曾经看懂过,可以参考原博客

     

    ⑨SAM的构造过程

    设当前字母为c,从上一个点las转移过来,当前新开一个点np,endpos多出一个{n}来

    先考虑转移,为了最大程度的利用节点,

    只对las的祖先节点中,计当前祖先节点为p,

    若不存在字母c的转移的点,对其进行转移到np的操作,

    并令p回跳到p的父亲,最终p停留在了某个节点

     

    以下分三种情况,实际上是(1)(2)两种情况,其中(2)分为两种子情况

     

    (1)c是没出现过的字符,这样回跳的时候一定会回到根,这里计根为1号节点

    根代表了空串,其endpos集合为{1,2,...,n},

    因此,c所在节点np构成了一个新的endpos集合{n},直接令fa(np)=1

     

    (2)停留在了中途某个点,此时点p存在字母c的转移,所以停下了,

    这其中分成两种子情况,计q为p通过字母c能转移到的点,len[q]是q中最长串的长度

     

    ①若len[q]=len[p]+1,由于p是las的祖先,p的串一定是las串的后缀,

    np比las多了一个字母c,q比p多了一个字母c,且q最长的串是p最长的串的长度+1,

    这表明,在p的串后面补一个字母c,其仍然是 在las串后面补一个字母c 的后缀,

    则q的串也是np串的后缀,q的endpos一定是np的endpos的超集,令fa(np)=q即可

     

    ②len[q]>len[p]+1,由于len[q]>=len[p]+1(是由p的串补了一个字母c而来),既然不等于,就一定大于

    说明q中的串分成了两部分,长度=len[p]+1的那些串x,由①,是np串的后缀,其endpos多出了{n}

    长度>len[p]+1的那些串y,不是np串的后缀,其endpos没有变化,

    而q是np在往上回跳的过程中,第一个包含了np的所有endpos的集合的点,

    既然不能表示,就考虑将q拆成两部分,

    一部分是x串集合构成的点,是新开的点,记为nq,有len[nq]=len[p]+1

    另一部分是y串集合构成的点,保持原来的q不变,

     

    起先,令nq的所有自动机转移关系(所有ch节点)等于原先的q,这样做可行的原因是:

    nq是q的后缀,后续在加入新的字符z时,设其跳到状态nr,

    由于nq和q只有碰到字母c时有区别,而z不等于c(设z=c,则nr是第一个包含了np的所有endpos的点,与nq是第一个包含了np的所有endpos集合的点矛盾),

    故没有受到新字母c的影响,所以二者唯一的区别endpos{n},没有给后续的nr的状态带来影响

     

    然后考虑fa的关系,nq是旧q的一部分,fa(nq)=fa(q),新q比nq长,可以令fa(q)=nq

    构建这个nq节点的意义在于表示np,所以令fa(np)=nq

     

    旧q的儿子(转移关系ch)原封不动保留到了新q和nq中,考虑fa的改变

    原先有一些节点指向q,但现在nq成为了q和np的fa,这些点应该指向nq,

    所以应从p往其祖先回跳,若其碰到字母c的转移为q,就应将其改为nq,

    对于没有通过c转移到q的那些祖先节点,其一定指向了nq的祖先,故不用修改

    心得

    感觉自己死抠知识点的证明,不做题,没啥大的意义,

    有些知识点感性理解一下就好了……

    但总之思路来源的博主写的很好,

    满足了我这个zz对于原理的一切幻想……

     

    去年8月、11月自学过SAM的原理,但是后来没做题,就渐渐忘了,

    现在想想,SA前年当时花了四五天抠原理,但现在也只记得rank、sa、height数组是干啥的了,

     

    实际上,SAM的情况就分三种,代码也很短,掌握了性质就可以了……

    证明什么的,除了O(n)的点数和边数的证明略复杂以外,剩下的还好……

    没必要每次做题前都复习一下证明,更何况这玩意比SA做题直接很多……

    展开全文
  • 后缀自动机概述

    千次阅读 2018-09-12 19:59:06
    如果对后缀自动机有一定了解,这几篇文章对你可能会有些许帮助: 后缀自动机学习指南 loj上的后缀自动机讲解 一些题目 听说对拆点讲解很详细 以题目为主,当然也有一些讲解。下面说一下我对后缀自动机的理解。....

    如果对后缀自动机有一定了解,这几篇文章对你可能会有些许帮助:
    menci’s后缀自动机学习笔记
    后缀自动机学习指南
    loj上的后缀自动机讲解
    一些题目
    听说对拆点讲解很详细
    127~132周

    以题目为主,当然也有一些讲解。下面说一下我对后缀自动机的理解,不给出详细证明。

    后缀自动机的特点

    首先,后缀自动机是一种有限状态自动机,他可以识别且仅识别一个字符串的后缀。但是这不并不是后缀自动机强大的地方,我可以说如果把AC自动机反向插入我同样可以做到这一点。

    后缀自动机真正的用处在于:它可以识别一个串的所有子串。

    非常优秀的是后缀自动机只会有 O(n) O ( n ) 个节点,也就是说在字符集看做常数的情况下,对于后缀自动机的构建可以做到 O(n) O ( n )

    后缀自动机不同于AC自动机的地方在于:它并不是一棵树,不看prarent链的话,后缀自动机是一张DAG,这就让后缀自动机每一个节点的意义玄妙了起来。

    后缀自动机每一个节点代表什么?

    定义一个子串的所有出现位置结尾的集合为这个子串的right集合。
    每一个节点识别的子串right集合相同,right集合相同的子串用同一个点接受。有一个很有意思的性质是right集合相同的字符串他们的长度一定是连续的。可以感性理解一下,aba和ba,aba出现的位置ba一定出现过,所以ba出现的位置数一定大于等于aba。

    后缀自动机的parent链是什么?

    如果B节点的right集合包含A节点right集合的最小集合,那么A节点有一条parent链连向B节点。可以把parent链当做fail链,但是他们之间有一些微妙的区别。
    构造的意义:顺着parent链跳可以逐渐增大right集合以便找到所有可以转移的状态。
    匹配的意义:我在匹配时记录已经匹配的长度,和当前在哪一个节点,那么我就可以知道我匹配最长是哪一个串,跳parent链时通过增大right集合,减小匹配长度,从而找到合法转移。这个等一会儿详细讲。
    parent链是一棵树,它组成了原串反串的一棵后缀树(这里不研究后缀树)。

    举个例子吧:abb

    a:1
    ab:2
    b:2,3
    bb:3
    abb:3

    我们把right集合相同的放在一起:
    1,a
    2,ab
    3,b
    4,abb,bb
    把子集包含的连上parent链(红色代表parent链),这样我们就得到了一个后缀自动机:
    这里写图片描述
    我们满足上面的条件就构造出了一个后缀自动机。
    可以证明对于任意串满足上面的条件都可以构造一个后缀自动机。

    如何构造一个后缀自动机?

    后缀自动机是一个增量算法,也就是说已经构造出了 s[1,i] s [ 1 , i ] 的后缀自动机,现在要构造 s[1,i+1] s [ 1 , i + 1 ] 的后缀自动机。
    对于每个节点记录一下它的转移,接受的最长串(len)和parent链(p),每次构造完之后记录一下到达的节点在哪儿(las)

    加入的时候肯定要有一个节点接受整个串,新建点x的right集合为{i+1},同时赋值len=i+1。
    right集合含有i的状态都可以转移到新建节点。发现las节点的right集合正好是i,根据上面的性质las节点的parent指向right集合包含i的节点,所以我们顺着las的parent链可以遍历所有right集合包含i的节点。

    这些点都应该有一个向x的 s[i+1] s [ i + 1 ] 的转移。

    下面分3种情况讨论:
    1.如果顺着parent达到了空节点,那么所有right集合含有i的节点都增加了向x的一个转移。到达空节点即可结束。
    2.到达了一个本来就有一个 s[i+1] s [ i + 1 ] 转移的节点y。设y向 s[i+1] s [ i + 1 ] 转移到q,那么right集合和q相同的子串已经被q接受,q的right集合是包含i+1最小集合,所以x的parent链连向p。
    3.但是按照2的做法会有一个问题:
    这里写图片描述
    这个后缀自动机是错误的,可以发现ab,b的right集合并不相同。
    那究竟是什么情况让我们构造出了这样一个错误的自动机呢?
    其实我们要让自动机新接受abb,bb,b三个串,并把它们分配给对应的节点,我们向前跳发现长度小于等于1的串(也就是b)已经被接受过了。q这个点的right集合里应该增加一个i+1。于是发现一个问题,q本来不止接受abb的后缀,它还多接受了一个串ab,ab的right集合并没有改变,但b改变了。本来right集合相同的串变成了不同的,但是我们用一个点接受,就产生了错误。
    换一种说法,我们让x接受长度大于y的len+1的串,q接受[?,len+1]的串。但是q并不只接受[?,len+1]的串,q本来接受了一个长度大于len+1的串。这些长度大于len+1并不是y的转移,所以不是abb的后缀,这些串就不合法。
    分情况讨论:

    y的len+1 = q的len
    这样按2的方法做。

    y的len+1 < q的len
    我们强行构造一个点让它接受[?,len+1]的串。我们用q复制一个点nq,nq的所有状态等于q的状态。沿着y的parent链向上找,把所有向q的转移转向nq。这样nq就接受了[?,len+1]的串的串,剩下的q就接受了[len+2,?]的串。q的parent链指向nq,x也指向nq。因为nq的riight集合包含q的和x的,所以把q和x的right集合指向nq。很显然,nq的len赋值为y的len+1

    这样我们就构造了出了一个后缀自动机。

    如何使用这个后缀自动机呢?

    首先我们可以知道一个串是否作为模板串的子串出现过,因为这个自动机可以识别模板串的所有子串。这是后缀自动机的一个最简单的应用。

    后缀自动机的强大之处在于:它可以计算每个子串出现次数。

    怎么做?把非复制节点出现次数定为1,这个节点出现一次,它沿parent链向上的点都会出现一次。于是我们就可以求parent链的拓扑序向上递推。

    每个点会有一个值,代表这个点管理的所有子串出现了那么多次。并且一个点x管理哪些子串呢?长度为(x的parent的len+1到x的len)。

    这样我们就可以在后缀自动机里匹配了。就像AC自动机匹配即可。但是有一个问题,走到一个点时并不代表匹配了这个节点管理的所有字符串。所以我们需要额外记录一个表示当前匹配长度的变量。这个变量与x的len取一个较小值就好。

    试一试吧:

    找相同字符

    写了这道题会对后缀自动机有一个大概理解,这里不赘述做法。

    code:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    struct lxy{
        int to[26],p,len,k,num;
    }a[400005];
    
    int cnt=1,las=1,len;
    int tax[200005];
    int tp[400005];
    char s[200005];
    long long ans;
    
    void insert(int c,int w){
        a[++cnt].len=w;a[cnt].num=1;
        int i;for(i=las;a[i].to[c]==0&&i!=0;i=a[i].p) a[i].to[c]=cnt;
        las=cnt;
        if(i==0){
          a[cnt].p=1;return;
        }
        int q=a[i].to[c],nq;
        if(a[i].len+1==a[q].len){
          a[cnt].p=q;return;
        }
        nq=cnt+1;for(int j=i;a[j].to[c]==q;j=a[j].p) a[j].to[c]=nq;
        a[nq]=a[q];a[nq].num=0;a[nq].len=a[i].len+1;
        a[q].p=nq;a[cnt].p=nq;las=cnt;cnt++; 
    }
    
    void querytp(){
        for(int i=1;i<=cnt;i++) tax[a[i].len]++;
        for(int i=1;i<=len;i++) tax[i]+=tax[i-1];
        for(int i=1;i<=cnt;i++) tp[tax[a[i].len]--]=i;
    }
    
    void matchit(int u,int pos,int l){
        a[u].k++;ans-=1ll*a[u].num*(a[u].len-l);
        if(s[pos]==0) return;
        for(;a[u].to[s[pos]-'a']==0&&u!=0;u=a[u].p);
        if(u==0) matchit(1,pos+1,0);
        else matchit(a[u].to[s[pos]-'a'],pos+1,min(l,a[u].len)+1);
    }
    
    int main()
    {
        scanf("%s",s+1);len=strlen(s+1);
        for(int i=1;i<=len;i++)
          insert(s[i]-'a',i);   
        querytp();
        for(int i=cnt;i>=1;i--) a[a[tp[i]].p].num+=a[tp[i]].num;
        scanf("%s",s+1);
        matchit(1,1,0);
        for(int i=cnt;i>=1;i--) a[a[tp[i]].p].k+=a[tp[i]].k,ans+=1ll*a[tp[i]].k*a[tp[i]].num*(a[tp[i]].len-a[a[tp[i]].p].len);
        printf("%lld",ans);
    }

    更多的题目可以参见文章开头的链接。

    展开全文
  • 本博客仅记录个人对后缀自动机的一些理解,没有入门详细推导等内容。 可以参考这两篇博客: 后缀自动机 (SAM) 学习笔记 后缀自动机 (SAM) 理解 后缀自动机到底记录了什么?由于一个字符串的任意一个子串可以表达为...
  • 题目大意:给出一个长度为 nnn 的字符串 sss,每个字母都有一个权值,现在要求所有本质不同子串中权值和第 kkk 大的权值 题目分析:如果没有本质...在后缀自动机中,每个节点代表的实质上就是一个本质不同的子串,而其
  • 后缀自动机的模板

    2018-10-15 21:57:42
    后缀自动机真是个好东西 #include &lt;bits/stdc++.h&gt; #define cl(a) memset(a,0,sizeof(a)) #define ll long long #define pb(i) push_back(i) #define sc(x) scanf("%d",&amp;x) using ...
  • 后缀自动机可视化 交互式应用程序,用于使用可视化单词的后缀自动机的构建过程。 (正在进行中)。
  • 后缀自动机构造后缀树

    千次阅读 2018-07-12 23:23:52
    我们参照这个图 反串建立后缀自动机的时候我们尝试沿着par树行走 发现反串的par树其实相当于原串的一些前缀 然后每次跳par树的时候都相当于在找一个后缀的前缀 然后那么如果要看后缀树上表示的边到底压缩了哪些...
  • 算法学习:后缀自动机转后缀树转后缀数组 引入 其实这是一篇水文 想要学后缀自动机的话去查2012年noi冬令营陈立杰讲稿 顺便说一句,讲稿上有一些错误,多翻几篇博客加深理解。 今天这里主要要讲的是后缀...
  • 后缀自动机总结

    千次阅读 2016-06-02 21:53:41
    后缀自动机总结 后缀自动机的构造和相关性质及复杂度证明可以看陈老师的ppt 时间复杂度据说可以用均摊分析证明是O(n)的 一开始看直接看陈老师的ppt确实有点难以理解,但是陈老师的ppt确实是讲的最正规的一个 ...
  • 后缀自动机 笔记

    2017-11-07 20:50:44
    后缀自动机是一棵trie树。 给出一个字符串S,对于S的一个子串s,Right(s) 代表一个集合,为s在S中所有出现的结束位置集合。 以S=”aabbabd”为例,Right(“ab”) = {3, 6},因为”ab”一共出现了2次,结束位置分别...
  • 描述 小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。 神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集,顾名思义,这部作品集里有许多作品,但是所有的作品...
  • 后缀自动机建树过程

    2015-01-29 22:46:21
    SAM建树过程 AC自动机Trie 图的建立过程 详细的图示
  • 后缀自动机简介 学习自这里 这里只是为了背板而写的简介 定义 对给定字符串s的后缀自动机是一个最小化确定有限状态自动机,它能够接收字符串s的所有后缀。 通俗点说,后缀自动机就是一种自动机废话 ,它...
  • 后缀自动机基础应用

    2018-07-26 18:32:45
    本博客讲解后缀自动机基础应用,而不说明定义、构建等内容。 构建代码如下:(跑得飞慢) struct node { node* ch[26], *f; int len, siz; // siz即Right集合大小 }; node* _nd = (node*)malloc(SIZE...
  • 后缀自动机初探

    千次阅读 2016-05-16 22:15:46
    定义给定字符串S, S 的后缀自动机(SAM)是一个能够识别S 的所有后缀的自动机一些记号 trans(s,x):状态s走x转移到达的状态 reg(s):状态s能接受的状态,即trans(s,str)属于end的所有str 功能 识别后缀:trans(init,...
  • 我们先对S建立后缀自动机, 然后从S的起点u开始, 再记一个长度L, 添加T[1 ~ LenT] 若存在子节点意味着添加当前字符后, 我们可以得到下一个状态,此时令状态u = next[u][c], L++. 若不存在, 即不断跳lnk[u],...
  • 先用SAM建出的后缀树的性质,求出每个endpos集合的大小。 然后用线段树或线性更新求出每个长度出现次数的最大值即可。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int ...
  • 之前网络赛跟队友合体出的题,当时我写的后缀自动机,他写的主席树,hhh! 现在我会写主席树,他会写后缀数组,于是各自独立的A了!并且我跟之前网络赛时的解法还不完全一样 巨佬队友bxd的后缀数组+主席树解法 题意...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,691
精华内容 5,876
关键字:

后缀自动机