后缀自动机

后缀自动机

 这里推荐一篇博客

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

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

时间内解决。

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

为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中仅作为w的后缀出现。

 

证明是显然的。

 

引理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，所以这一过程的时间复杂度是线性的。

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

代码实现

1.储存后缀自动机的结构体

struct sd{
    int turn[26],len,link;
}t[2000005];

turn[i]-->每个节点的转移，turn[i]不为0时，则指向所转移的字符的位置

len-->每个节点储存的最长后缀长度

link-->每个节点的后缀链接

2.建立后缀自动机

void build(char v)
{
    size++;
    int gg=size,k=last;
    //size记录节点个数，last记录上一个节点编号，同时因为存在复制节点，所以size不一定等于last 
    t[gg].len=t[k].len+1;
    for(;k!=-1&&!t[k].turn[v-'a'];k=t[k].link)//寻找后缀链接的最终点，所有节点都连一条转移 
    t[k].turn[v-'a']=gg;
    if(k==-1)//如果找到了根节点，那就直接连一条链接便完成了 
    t[gg].link=0;
    else//如果存在一个节点有当前插入点的相同转移那就搞事情 
    {
        int node=t[k].turn[v-'a'];
        if(t[node].len==t[k].len+1)//判断是否需要复制节点 
        t[gg].link=node;
        else //开始复制一个相同节点来维护后缀自动机 
        {
            size++;
            t[size].link=t[node].link;
            t[size].len=t[k].len+1;
            for(int i=0;i<26;i++)
            t[size].turn[i]=t[node].turn[i];
            //新增节点除维护最长后缀长度修改之外，其余与被复制节点相同 
            for(;k!=-1&&t[k].turn[v-'a']==node;k=t[k].link) //将之后的链接就直接连在复制节点上了 
            t[k].turn[v-'a']=size;
            t[gg].link=size;
            t[node].link=size;//node也连一个链接到复制节点 
        }
    }
    last=gg;
}

这就时后缀自动机建立的方式，建立后缀自动机时算法的关键

其余的操作根据需要的不同就不再赘述了

后缀自动机一起独特的存储方式可以实现数量相当可观的字符串题目，可以说是处理字符串题目的神器了

所以学好后缀自动机是处理字符串题的关键

在这里留一道后缀自动机模板，供初学者练习使用

https://www.luogu.org/problemnew/show/P3804