史上最通俗的后缀自动机详解

$by\space KesdiaelKen$ 网上的解析都太巨佬了，搞得本蒟蒻看了2天才看懂…… 感觉本文会比网上大多数文章通俗易懂很多，并且会对程序作具体解析，适合初学者阅读。 本文共分四节，内容大致~~符合政治答题思路~~如下：①干什么以及基本定义②基本思想以及特殊定义③构造方法以及程序具体解析④基本应用以及类比。 **虽然这篇文章是针对初学者，但是读这篇文章之前，请务必了解$trie$、基本的集合知识、基本字符串知识和基本图论知识。如果需要看懂第四节的一些内容，还需要了解后缀数组。** **本文只是对后缀自动机最基本的思想与构造方法进行详细解析，对于更高级的扩展层面不会多加分析，想了解此方面的同学请自行查找资料（clj的ppt等）。** **本文很多的表述会在上文中解释，所以如果需要完全理解本文，请务必仔细按顺序阅读。** **本文借鉴了许多其他文章的表述方法，如有雷同，请见谅。** ## 1. 后缀自动机要干什么 如果要在一个DAG（有向无环图）上表示出一个字符串的所有子串，应该怎么办？ 很显然，一个最简单的方法是建立一个trie（字典树），如图。（对于$aabab$建trie，红色为根，黄色为终止节点，边的方向未画出） 方法是将原串（$n$为其长度，下文默认）的每一个后缀都加入字典树。 大家请观察一下这个字典树，看看它有什么性质。 我们能够直观地总结出来的性质有： 1. 有一个源点，若干个终止点。边代表在目前的字符串后加上的字母。从源点到任意一个节点的任意路径可以形成一个字符串。 2. 从**源点**到任意节点的任意路径形成的字符串均为原串子串。从**源点**到任意节点的任意路径**不能**形成的字符串均**不**为原串子串。（简单来说，这个图可以表示，且仅可以表示出原串的所有子串） 3. 从源点到任意终止节点的任意路径形成的字符串均为原串**后缀**。 4. 从源点出发的任意两条不同路径形成的字符串不相同。 如果满足以上四个性质，那我们便可以用此DAG处理许多事情。比如，判断某一个串是否为原串的子串（做法：从源点跑这个串，跑到$NULL$就说明不是子串）、不同子串个数（做法：DAG上DP）等（后缀自动机可以处理的问题则多得多，因为它有更特殊的性质，这个之后再说）。 **但是**，我们发现了一个问题。这样建立的DAG节点数是$O(n^2)$的。当$n$很大时，这样的复杂度无法接受。事实上，我们发现图中许多的节点都可以合并，比如：$b$之后的部分与$ab$之后的部分完全一致，可以合并。 我们现在的任务是，构造一个节点数、边数尽量少的DAG满足以上四点条件。 ## 2. 后缀自动机特别在哪 先来看一些定义吧。**（这部分是后缀自动机的精髓，也是后缀自动机真正厉害的地方，至于发明者是怎么想到的我完全不能想象（可能是我太菜了））** 对于一个子串，它在原串中可能出现在若干的位置。而一个子串$p$出现的这些位置的右端点标号组成的集合，我们称之为$endpos(p)$（例如原串为$abcab$时，$endpos(ab)=\{2,5\}$） 现在我们需要证明三个结论，它们将在算法中发挥重要的作用。 ### _1.如果两个子串的$endpos$相同，则其中子串一个必然为另一个的后缀_ 设较短的一个串为$t$，较长的一个为$p$，则当命题不成立时，二子串在后$len_t$（$t$的长度）个字符上一定有至少一位不同。但是，因为$t$已经在$endpos(t)$的这些位置匹配上了，即后$len_t$个字符已经在这些位置完全匹配，所以不可能出现这种情况，否则在这些位置上$p$将不能匹配，$endpos(p)$必然不等于$endpos(t)$（实际上是完全不相交）。所以命题得证。（其实这个从直观上意会一下就可以了，证明反而更加不清晰。） ### _2.对于任意两个子串$t$和$p$（$len_t\le len_p$），要么$endpos(p)\in endpos(t)$，要么$endpos(t)∩endpos(p)=$∅_ 实际上是结论$1$的逆命题，说明方法同上，分$t$为或不为$p$后缀两种情况讨论。 ### _3.对于$endpos$相同的子串，我们将它们归为一个$endpos$等价类。对于任意一个$endpos$等价类，将包含在其中的所有子串依长度从大到小排序，则每一个子串的长度均为上一个子串的长度减$1$，且为上一个子串的后缀（简单来说，一个$endpos$等价类内的串的长度连续）_ 显然长度覆盖的区间是连续的，不可能存在空隙。后缀的命题可由结论$2$得到。 对于任意两个$endpos$等价类，它们不会同时包含同一个子串。 下文有一些地方直接用$endpos(i)$表示$endpos$等价类$i$中子串的$endpos$，请读者注意。 由以上三个定理，我们就可以得到一些延伸结论： ### _4.$endpos$等价类个数的级别为$O(n)$_ 这个命题比较重要。 对于一个**类（$endpos$等价类简称）**，根据结论$3$，其中有最长的一个子串（$p$）。在$p$第一个字符前添加任意一个字符（满足新形成的字符串为原串子串），得到的字符串必然不属于此类，因此会得到若干个新的类。我们由结论$2$得到新形成的字符串的$endpos$必然为$endpos(p)$的子集。并且在$p$前分别添加两个不同的字符，所得到的两个字符串的$endpos$必然完全不相交。所以对于此操作（在$p$前添加一个字符），我们可以认为是对一个原集合进行分割，分割得到几个新的集合，且保留原集合。当然，新的集合还可以继续分割，但是总的分割的次数（指断痕的个数，$\{1,2,3,4,5\}$分割成$\{1,3\},\{2,4\},\{5\}$的分割次数为$2$）不会超过原集合的大小，所以最终形成的集合个数也不会超过$2n$（线段树的分割方法为子集个数最多的分法）。 由此，因为一切$endpos$都是从$\{1,2,...,n\}$（$n$为原串长度）分割出来的，所以$endpos$等价类个数级别为$O(n)$。（这一部分看不懂可以参考clj的ppt） 考虑**分割**关系。一个原集合分割成若干个子集的操作，是不是很像树的一个节点延伸出若干个子节点？我们发现，所有$endpos$等价类依靠这种分割关系，恰好可以构造出一个树形结构。（有时一个类的某些信息会在其儿子处丢失，例如图中$\{1,2,4,6\}$的儿子是$\{2\}$和$\{4,6\}$，它们丢失了位置$1$的信息。至于原因，第四节会讲。）（下图例子的原串为$aababa$） 于是，类之间就有了父子关系。 ### 我们称这棵树为parent tree 下一个结论 ### _5.一个类$a$中，有最长的子串，也有最短的子串，我们称最长子串的长度为$len(a)$，最短子串长度为$minlen(a)$。对于存在父子关系的两个类，设$fa(a)$表示类$a$的父亲（也是一个类）。则：$len(fa(a))+1=minlen(a)$_ 这个结论很显然，从我们推理结论$4$的步骤中就可以看出。在一个类中的最长子串前再添加一个字符，形成的字符串就必然属于其儿子中的一类，且这个新形成的字符串肯定是它所属的类中最短的一个。 因此，我们只用在parent tree中保存$len$即可，$minlen$可由其父亲推出来。我们定义$longest(s)$表示$s$类中的最长子串，$shortest(s)$表示$s$类中的最短子串。 我们把每一个类的最长子串写在节点旁，以方便理解。（原串还是$aababa$） 现在，我告诉大家一个令人震惊的事情：我们要的后缀自动机的节点就是parent tree中的节点！~~妙啊~~（可以认为是parent tree和后缀自动机两个图共用同样的节点）只不过边与parent tree中的不同。其中空串所属的节点（parent tree的根）就是后缀自动机的源点。而终止节点便是最大子串（整个原串）所属于的节点（**属于：这个节点的类包含此子串**），以及其在parent tree上的祖先（标橙）!为什么要这么做呢？因为其节点数很少，且边数也很少（下有证明）。最重要的是，这样形成的图依靠parent tree，有非常有趣的性质，这个本节最后会说。[](https://cdn.luogu.com.cn/upload/pic/48737.png) 我们需要考虑如何建立parent tree，以及如何在这些点上连后缀自动机的边，使得**从源点出发到达点$i$的任意一条路径形成的字符串均属于节点$i$所代表的类。** 完成的后缀自动机如下（蓝色为后缀自动机的边）： （太丑了是吗……之后的部分会给更好的图。其实这个图形不符合之后我们讲的后缀自动机的形态，不过这里只是为了展现后缀自动机有多么复杂而已……） 还可以理解为，延parent tree的边往下走是在字符串前面添加字符，延自动机的边往下走是在字符串后面添加字符。在第四节我们将看到，正是因为上面的特性，parent tree主要用来求节点（即各个字符串）的性质，而后缀自动机本身则主要用来直接跑字符串。 我们先简单说明一下满足条件的后缀自动机是一定存在的。还记得第一节提到的后缀自动机必须满足的四个基本性质吗？对于前三个后缀自动机可以满足。对于第四个，由于上文说道，对于任意两个$endpos$等价类，它们不会同时包含同一个子串，因此到达任意两个不同节点可能形成的字符串均不会重复。现在我们只需要说明边的正确性即可。若对于一个类的所有子串，我们都在它们后面添加一个相同的字符，则得到的所有新的字符串必定都属于另一个相同的类（想想是不是这样）。因此边存在正确性。所以后缀自动机存在。（这里的解释还是不够严谨，如果需要严谨解释可以用类似数学归纳法的方法结合程序说明。因为程序是递推的，初始状态的后缀自动机满足条件，程序正确，所以加入一个新的字符后的后缀自动机也满足条件。这里如果看不懂，可以看完第三节后再尝试理解） 另外，得到点的数量级还不够。下面再证一个比较重要的结论： ### _6.后缀自动机的边数为$O(n)$_ 考虑对于一个后缀自动机：先求出其任意一个生成树，舍弃其其它边。我们知道，后缀自动机上有若干个终止节点。于是我们便从每个终止节点往回跑所有属于它（这个类）的子串（从终止节点跑其实就是跑原串的后缀）。注意这里的往回跑是指：对于一个子串，按照原本后缀自动机到达其的唯一路径经过的边往回跑，而非只考虑边的字符，因为可能有多条代表相同字符的边指向同一个节点。 对于每个终止节点：我们按一定顺序跑遍属于它的子串。如果能顺利跑回源点，则跑下一个子串。否则，连上本应该跑回的边，沿它跑回下一个节点。此时，从这个节点出发，一定有一条或多条路径（经过现存的边）回到源点（因为有树的基础结构），则我们往回跑其中任意一条路径。这样，实际走的路径形成的字符串不一定是原本希望跑的子串，但是因为加了一条新边，且路径是从同样的终止节点开始的，所以得到的字符串必然属于此类，且未被跑过。我们只需要将这个字符串在将来要跑的子串中划掉即可。之后重跑我们原本希望跑的子串，直到真正顺利跑完这个子串，再按顺序跑下一个子串。可以发现，我们在此过程中增加的边数不会超过此节点$endpos$的大小。 这样，当跑完所有终止节点时，在原本的生成树上增加的边不会超过后缀的个数，即$n$个。而此时，增加了边的后缀自动机已经完整了。于是，生成树的边数加$n$，数量级为$O(n)$。（这里与clj的ppt上的证明方法是刚好相反的，clj的证明是从源点开始向各个终止节点跑后缀，而非从终止节点往回跑到源点。） 为了方便理解以上内容，我们再画图讲解一下。下文的图解内容完全模拟上述证明方法。 以上是原串$abcd$的后缀自动机，我们随机取它的一个生成树： 终止节点只有$5$一个。属于$5$的后缀有（$abcd,bcd,cd,d$）。我们按照（$cd,d,abcd,bcd$）的顺序跑后缀。跑$cd$时，我们发现可以直接沿$5-4-1$跑回源点，所以跑下一个子串。 跑$d$时，我们发现确实有一条$d$边连向$5$,但是跑这条边回到的点的$endpos$是$\{3\}$，并不是应该的$\{1,2,3,4\}$（$d$往回跑一个字符就是去掉其结尾字符得到空串，$endpos$为$\{1,2,3,4\}$）。所以此时我们需要连一条边，从代表$\{1,2,3,4\}$的$1$连到$5$： 跑$abcd$时，我们先跑回$4$节点，符合条件（去掉末尾剩下$abc$，$endpos$为$\{3\}$，属于节点$4$）。接下来，我们发现无法继续跑回，于是增加从$3$到$4$的$c$边： 此时剩下$ab$，到达点$3$，我们还是没办法跑它跑回源点。但是，我们不一定要跑它跑回源点，只要能跑回源点就行了。于是，我们往回跑$1$到$3$的边（代表$b$）。那么现在，我们就等于跑了$b+c+d=bcd$的后缀了，它是一个之后我们要跑的后缀，我们把它划掉。然后接着往回跑$abcd$，连上$1$到$2$的边： 跑$bcd$时，我们发现它已经被划掉了，所以不用跑。 这样，我们跑完了所有后缀，增加了不多于$n$条边，完成了后缀自动机。（这个例子应该看得懂吧） 在进入下一节之前，我们再来说一说后缀自动机的特殊性。前面说到，后缀自动机的一般性可以让我们处理的问题有：判断子串，计算不同子串个数等。 而后缀自动机的特别之处在于parent tree与节点本身的特殊意义（$endpos$本质为**在原串中出现的位置**的集合）。这就导致可以通过在parent tree上DP得到每一个类中的子串**和在原串中出现的位置相关**的一些信息。例如，出现的次数，第一次出现的位置，出现在某个位置之后的次数等。这就导致后缀自动机可以处理更多类型的题目。 最后，我们梳理一下后缀自动机的性质，这些性质可能会对理解后缀自动机的构造方法有很大作用： 1. 有一个源点，边代表在当前字符串后增加一个字符。 2. 每个点代表一个$endpos$等价类，到达一个点的路径形成的子串必须属于此点的类。 3. 点之间有父子关系，到达点$i$的所有字符串的长度都必然大于到达$fa(i)$的所有字符串的长度，且到达$fa(i)$的任意一字符串必为到达$i$的任意一字符串的后缀。 ## 3. 后缀自动机怎么构造 说了这么多，终于讲到构造了。 我们先简单描述一下后缀自动机的形态。后缀自动机大概是长这样子的 下面那整齐的一行节点表示的就是各个前缀所属的节点。显然，对于任意一个前缀，它在它所属的类中长度是最长的（不能再在其前面添加字符）。而相邻两个前缀所属点之间也肯定有连边。当然，不相邻的节点之间也会有一些边。所以我们把这些节点排成一行，方便观察。 而上面那些零零散散的节点则是不包含任意一个前缀的节点，有一些边连上去，有一些边连下来（注意，连上去的边与连下去的边分割没有那么明显，图只是示意，不要误解），它们之间还有一些连边。这就是后缀自动机的基本结构。 后缀自动机的构造是在线的，即我们通过不断添加单个字符的方式构建后缀自动机，时刻调整其状态。简单来说，我们把原串拆成一个个字符，按顺序塞进后缀自动机里。 先上程序吧。 ``` struct NODE { int ch[26]; int len,fa; NODE(){memset(ch,0,sizeof(ch));len=0;} }dian[MAXN<<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[MAXN];int len; int main() { scanf("%s",s);len=strlen(s); for(int i=0;i<len;i++)add(s[i]-'a'); } ``` （很多教材都没有很好地解释循环在条件满足时停止的原因，这也是本人当初不理解程序的重要地方之一，因此下文会花较大篇幅讲解循环的意义。） 相信大家肯定看不懂吧……（网上有博客说很好理解？？？） 但至少主函数内的东西应该是看的懂的，即读入原串，然后通过在线的方式一个个加入字符，通过$ans$函数构造后缀自动机。 那么$dian$就是后缀自动机里的节点。结构体里的$len$和$fa$与第二节里的定义一致。而$ch$则与$trie$里的边意义相近。 ``` void add(int c) { int p=las;int np=las=++tot; dian[np].len=dian[p].len+1; ``` 首先看第一行。$las$是什么？是未加入此字符前最长的**前缀**（整个串）所属的节点的编号，$tot$则是当前后缀自动机节点的总数。 新加入了一位字符$c$（减了$'a'$是为了方便塞进边里，可类比$trie$里对字符的处理）。我们设未加入$c$前的原串为旧串，加入$c$后的原串为新串。显然，此时新串的最长前缀（整个串）所属的节点显然不在原图中，因为原来的所有$endpos$都不可能包含这一位。而旧串的最长前缀就变成了新串的次大前缀。所以我们用$p$记录新串次大前缀（原串的最大前缀）所属的节点，然后新建一个节点$np$，存新的最大前缀所属的类。$len(np)$肯定就是新串的长度，即$len(p)+1$。 注意一下，加入$c$后，$endpos$可能发生变化的字符串只有新串的后缀（或者说，**旧串的后缀加$c$**）（它们无论在旧串出现与否，在新串中出现的次数一定会比在旧串中多$1$）。所以我们的任务就是处理好这些$endpos$发生变化的字符串（具体做法是遍历旧串后缀（事实上是遍历旧串的后缀自动机的终止节点），看看它们加$c$后$endpos$有没有改变）。另外，对于任意一个$endpos$变化的字符串，它的新$endpos$与原来$endpos$的差别只是多了一个$n$，即新串右端点的位置。因此我们判断一个串的$endpos$是否变化，只需要看其是否在新串最后出现即可。 ``` for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np; ``` 我们进行一个循环操作。这个循环操作进行下去的条件是：$!dian[p].ch[c]$（$!p$只是防止其跳出根节点），即$p$没有一条$c$的出边。而$p$每一次循环后会跳到$dian[p].fa$，即$fa(p)$。 首先我们得知道往上跳到底是干什么。我们知道存在父子关系节点包含的子串有后缀关系。那么，这个$p$跳$fa(p)$操作的意思即：一个是$longest(p)$（还记得$longest$是什么意思吗？定义在结论$5$的证明下面）的后缀，且与$longest(p)$所属类不同的最长串所属的类。（这里的$longest$改成$shortest$也无妨） 因为由一个节点往外连一条边就等于允许到达此节点的所有字符串往尾部添加一个新的字符。并且，由于$len(fa(i))+1=minlen(i)$，因此对于$i$和$fa(i)$，它们包含的子串的长度从大到小排序时也是连续的。所以我们把每一个节点想象成所有到达它的字符串的集合。那么，这个**跳$fa(i)$的操作可以理解为压缩地遍历一个串的所有后缀。**在这里，**$p=fa(p)$即从长到短遍历旧串的所有后缀**。 对于节点$p$，如果它没有$c$边（即$''longest(p)+c''$非旧串子串），那么引一条新边到$np$。这里用上面的思想解释，即将所有是旧串后缀且在其后面加$c$形成的新字符串不是旧串子串的字符串往新串的最长后缀所属节点连一条$c$边。这样的做法显然是正确的，因为这些后缀加了$c$产生的新字符串不是旧串的子串，但是因为是旧串的后缀，加上$c$后必然是新串后缀，即它们的$endpos=\{n\}=endpos(np)$。因此向$np$连边是正确的。 注意循环的终止条件。如果长度再短，这些旧串后缀加$c$形成的新字符串就已经在旧串里出现过了，显然与新串最长前缀的$endpos$不同，所以不需要继续连边。 ``` if(!p)dian[np].fa=1;//以上为case 1 ``` 如果已经遍历完了旧串的后缀且它们加$c$一个都不是旧串的子串，就说明$c$实际上是一个在旧串中没有出现过的字符，因此不可能存在除节点$1$以外的祖先，直接令$fa(np)=1$。 ``` else { int q=dian[p].ch[c]; if(dian[q].len==dian[p].len+1)dian[np].fa=q; ``` $p$在第一个有$c$边的祖先停下了（停止原因已在上文说明）。此时，我们将$q$设为$p$的$c$出边到达的节点。此时，我们将做一个非常有趣的判断：$len(q)$是否等于$len(p)+1$。这个判断是什么意思呢？因为$''longest(p)+c''$是新串后缀，又因为$len(q)==len(p)+1$，所以$longest(q)==''longest(p)+c''$，所以$longest(q)$是新串后缀。而$q$类中的所有串都是$longest(q)$的后缀，所以到达$q$的所有串都是新串后缀，它们的$endpos$都增加了$n$，因此到达$q$的所有串的$endpos$一致，符合后缀自动机的定义。由于$q$是我们找到的第一个与$np$不同的且有后缀关系的节点，我们把$fa(np)$设为$q$。 此时我们还需要说明一下为什么不用继续跳$fa$，判断其他旧串后缀的情况。因为$p$继续跳$fa$，引出的$c$边到达节点$q'$。那么，$q’$必然是$q$的祖先，那么原先到达$q'$的串的$endpos$肯定都增加了一位$n$，满足_到达同一节点的字符串$endpos$都相同_的性质，不需要处理。到此，新串的后缀都已经被检查过了。 为了方便理解以上$case 1$和$ case 2$，我们举个例画图来讲解一下。 以$aaba$为例。初始只有一个源点： 加入$a$，创建节点$2$，$len(2)=1$，连边，$1$没有$a$的出边，跳到$0$。所以进入$case 1$，直接设$fa(2)=1$。（蓝边表示parent tree，红字表示$len$） 加入$a$，创建$3$。$2$没有$a$的出边，所以连边，跳$1$。$1$有$a$的出边连向$2$，且$len(2)=1=0+1=len(1)+1$，所以进入$case 2$，直接$fa(3)=fa(2)$。 加入$b$。创建$4$。$3$和$2$和$1$都没有$b$的出边，连边。所以进入$case1$，直接$fa(4)=1$。 加入$a$，创建$5$。$4$没有$a$边，跳$1$。$1$有$a$边连向$2$，且$len(2)=len(1)+1$。所以进入$case2$，$fa(5)=2$。 如图便是$aaba$的后缀自动机，大家检查一下，看看符不符合后缀自动机的性质。 ``` 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 ``` 终于来到后缀自动机构造最难理解的部分了。 当$len(q)\not=len(p)+1$时怎么办？其实这个式子等价于$len(q)>len(p)+1$，因为$p$可以到$q$，所以$len(q)\ge len(p)+1$。 那么，$len(q)>len(p)+1$代表了什么呢？它代表了还有至少一个比$''longest(p)+c''$更长的串属于$q$。而这个更长的串必定不是新串的后缀，因为如果是，那么去掉其最后一个字符得到的字符串必然是旧串的后缀，且其长度大于$longest(p)$，因此应该先被跳到。然而事实并不是这样。所以，现在出现了一个问题：属于$q$的长度不大于$len(p)+1$的串是新串的后缀（$case2$说明过），但大于$len(p)+1$的串却不是。此时，到达$q$这个节点的字符串并不全属于一个类（准确来说，属于两个类，一类的$endpos$比另一类的$endpos$多出了一个$n$），出现了问题（$q$的$endpos$无法得到定义）。而现在，我们要想办法将其中一个类的子串移到另一个节点上，只保留其中一类的字符串，让$q$的$endpos$可以得到定义。 我们考虑把$endpos$多出了$n$的字符串转移。显然，旧串的后缀自动机中并没有$endpos$与其相同的节点（如果有，那$p$本来就应该连向它）。所以我们新建一个节点$nq$，让$endpos$多出了$n$的字符串转移到此节点。 新建了一个节点，要考虑它的连边，$fa$与$len$。 先考虑$len$。由上文我们知道，长度大于$len(p)+1$的字符串都不可能是新串的后缀。并且，$p$有一条连到$nq$的边。因此，我们把$len(nq)$设为$len(p)+1$。 然后考虑出边。由于$nq$只是$q$拆出来的一个点，我们考虑直接用$q$的边。这样做显然是正确的，因为把$nq$从$q$拆出来只是因为$nq$的$endpos$与$q$不一样。但是，在$q$后和$nq$后加同样的字符，得到的字符串必然属于同一个类（首先，它们之间必然存在后缀关系且在旧串中属于一个类。又因为这个类中的串必定不是新串的后缀，否则就应该先被跳到，没有受到新加入字符的影响，所以在它们新串中还是同属一个类）。 最后考虑$fa$。由于原来的$q$被拆成了两个点$q$与$nq$。$len(fa(nq))<len(nq)<len(q)$。又因为$fa(nq)$肯定为旧串中的$fa(q)$，因为在旧串中$q$和$nq$还未被分拆。因此，可以看做是$nq$插入到了这个父子关系中。所以我们让$fa(nq)$等于旧的$fa(q)$，然后让$fa(q)$等于$nq$，类似于链表的插入。 此时，我们考虑$np$的$fa$。这个$fa$肯定是$q$和$nq$之一，因为它们最先被跳到。$q$肯定是不行的，因为它的$endpos$没有$n$，而$endpos(np)$有$n$。所以$fa(np)$必为$nq$。 之后，我们进行一个类似$case1$的循环操作，不断往上跳$fa$。只不过，这里的判断条件变成了$dian[p].ch[c]==q$。意思即，因为$q$的$endpos$不包含$n$，而$''longest(p)+c''$的$endpos$必然含$n$，不符合后缀自动机性质，所以我们让这条边连向新的节点$nq$，这样显然是正确的（本就连向$q$，只是$endpos$多了一个$n$，所以连到$len$紧随其后的$fa(q)$，即$nq$）。 那么，为什么当$dian[p].ch[c]\not=q$时，可以不继续跳了呢？那是因为，这时$dian[p].ch[c]$的指向的点肯定是$q$的某个祖先（$p$变短了，并且$''longest(p)+c''$还是原来$''longest(p)+c''$的后缀，所以$q$与$dian[p].ch[c]$满足祖先关系（后缀和长度要求））。那么，我们知道$q$的父亲是$nq$，$endpos$包含$n$，因此$q$的祖先的$endpos$都包含$n$。所以再往上跳，$dian[p].ch[c]$都不会出现一个节点两种$endpos$的错误情况了。 另外说一下，程序里$dian[nq]=dian[q]$的语句是压缩的$fa$和边的赋值。可以拆分成： ``` strcpy(dian[nq].ch,dian[q].ch); dian[nq].fa=dian[q].fa; ``` 以上就是程序的基本思想。 我们继续上图吧（可以对照上面的讲解与程序看一看）。例子：$aababa$。前面$aaba$的图可以继续用。这是$aaba$的后缀自动机： 加入$b$，创建$6$。$5$没有$b$边，连边，跳$2$。$2$有$b$边连向$4$，但是$len(4)\not=len(2)+1$，（此时$ab$和$aab$都到达$4$，但二者$endpos$不同）所以新建节点$7$，从$4$复制$fa,ch$，$len(7)=len(2)+1=2$，然后令$fa(6),fa(4)$等于$2$。之后跳$fa$，把$2$连向$4$的边连向$7$，$1$连向$4$的边连向$7$。（尽梨了……ppt的曲线就是那么诡异） 加入$a$，创建$8$。$6$没有$a$的边，连边，跳$7$。$7$有$a$边连向$5$，但$len(5)\not=len(7)+1$，所以新建$9$，重复之前的操作。 以上便是构造后缀自动机的全部内容。下面，我们再来证明一些东西。第二节中，我们已经证明了后缀自动机的空间复杂度。现在让我们来证明后缀自动机构造的时间复杂度。 根据程序我们知道，可能超时的地方只有两个跳$fa$的循环。让我们一一证明它们的均摊时间复杂度是$O(n)$的。 ``` for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np; ``` 这是$case1$的循环。简单想想就知道，这个循环的真面目其实就是加边。因为后缀自动机构造的整个过程中，边数都不会减少，所以这里循环的次数应该与边数数量级相同，不会超过$O(n)$。 ``` for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq; ``` 这是$case3$的循环。这里显然就不能认为是加边了，所以我们得换个思路。是不是可以认为，我们在遍历连向$nq$的边？因为$nq$一个新建节点，所以下一次进行这个循环的时候，我们不会再遍历上一个$nq$的边。又因为所有边被遍历的均摊复杂度是线性的（本人并不怎么会证明，网上资料也不多，如果需要详细了解请参考更高级的教材）。于是，我们可以认为程序对每一个节点的入边都遍历了一次。因此，均摊时间复杂度与边数相同。 ## 4. 后缀自动机该怎么用 （下文将把后缀自动机和后缀数组进行对比，请未学习后缀数组的同学补一下，或者跳过一些内容） 后缀数组和后缀自动机能处理的相同问题很多，并且各自也有对方不能处理的问题。 后缀数组的时间复杂度是$O(n\log n)$。后缀自动机的时间复杂度是$O(n)$，可能常数会稍微大一点点，但应该还是必后缀数组快（取决于个人代码常数）。但是后缀自动机的做法往往比后缀数组无脑。 下文会列举几个后缀自动机可以解决的问题。如果后缀数组可以解决，也会列出简单解法。 ### _问题1：判断子串_ 直接在后缀自动机上跑边，跑完串还未跑到$NULL$则为原串子串。 后缀数组：跑出$sa$，然后从最小的后缀开始，一个个往后枚举，记录下当前匹配到的位置，如果匹配不上就下一个后缀，否则位置向后移一位。如果枚举完了后缀还没有完全匹配则不是原串子串。 ### _问题2：不同子串个数_ $DAG$上$DP$。对于一个节点$i$，$f[i]$表示从$i$出发的子串个数（不含空串）。那么，$f[i]$就等于$\sum_{(i,j)\in Edge}(f[j]+1)$。$f[1]$即是答案。 或者直接求$\sum(len(i)-len(fa(i)))$，因为后缀自动机上无重复字符串。 后缀数组：每一个后缀的长度减去其$height$之和。 ### _问题3:在原串所有子串中（相同的不算一个）字典序第$i$大的是哪个_（[P3975](https://www.luogu.org/problemnew/show/P3975)） 这题比较重要。 首先处理出每个节点的$endpos$大小，即每个类中的串在原串中出现的次数。考虑$dp$，$f[i]$代表$i$的大小。对于不包含任意一个个前缀的节点，$f[i]=\sum _{(i,j)\in parent \space treeEdge}f[j]$，因为比$longest(i)$前面多一个字符的所有字符串的$endpos$的并集必然等于$endpos(longest(i))$。而对于包含前缀的节点，$f[i]=(\sum _{(i,j)\in parent \space treeEdge}f[j])+1$，因为第$1$位的信息在加字符时丢失了。（这里是第二节遗留的问题，可以参考第二节的parent tree示意图来理解。因为parent tree上一个节点的出边（方向从$fa$到$ch$）相当于对此节点$endpos$的拆分，拆分方式为在此节点的$longest$前面添加字符。但由于此节点包含前缀，在添加字符时必将丢失此前缀位置的$endpos$（因为加上字符的子串已经大于前缀长度），所以丢失了$1$位信息，需要加回来（$update\space 2019.8.15$））（具体到程序来说，只需在$case1$里加一句$f[np]=1$即可） 然后$DP$出$g[i]$，表示从$i$出发的子串个数（不含空集且计算重复），则$g[i]=\sum_{(i,j)\in SAM\space Edge}(g[j]+f[j])$。 最后，在后缀自动机上$dfs$，按字典序遍历出边，排名还够的减去这边的所有子串，不够的跑到这条出边连向的节点，重复以上步骤。当排名变为非正数时输出跑过的路径形成的字符串。具体做法还请参考本题题解。 ### _问题4：判断两个串的最长公共子串_ 把两个串拼起来，跑后缀自动机。然后用类似于上面处理出现次数的方法，跑出一个子串在拼起来的串前半部分出现的次数和后半部分出现的次数。然后遍历节点，找$len$最大的前后出现次数都不为$0$的节点。以上思路还可以处理多个字符串的最长公共子串。 后缀数组：同样是拼起来，然后处理$sa$和$height$，对于每个后缀，找到其之后第一个属于另一半部分的后缀（可以$O(n)$做到，具体做法请读者思考），求它们的$lcp$，最后取最大值。 还有一些题目与方法本文可能未涉及到，请多多谅解。毕竟这只是给初学者看的文章，想要了解更高级的内容请自行寻找资料。 ## 后缀自动机思路精巧，处理问题多样，不失为字符串题目的好算法。