题解 P3804 【【模板】后缀自动机】

KesdiaelKen · 2019-01-20 14:20:29 · 题解

拷贝自本人写的史上最通俗的后缀自动机详解，本题的具体题解在文末。

FBI WARNING：本文大约有1w字，阅读全文大约需要60分钟……

网上的解析都太巨佬了，搞得本蒟蒻看了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(t)\in endpos(p)，要么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，有非常有趣的性质，这个本节最后会说。

我们需要考虑如何建立parent tree，以及如何在这些点上连后缀自动机的边，使得从源点出发到达点i的任意一条路径形成的字符串均属于节点i所代表的类。

完成的后缀自动机如下（蓝色为后缀自动机的边）： （太丑了是吗……之后的部分会给更好的图。其实这个图形不符合之后我们讲的后缀自动机的形态，不过这里只是为了展现后缀自动机有多么复杂而已……）

我们先简单说明一下满足条件的后缀自动机是一定存在的。还记得第一节提到的后缀自动机必须满足的四个基本性质吗？对于前三个后缀自动机可以满足。对于第四个，由于上文说道，对于任意两个endpos等价类，它们不会同时包含同一个子串，因此到达任意两个不同节点可能形成的字符串均不会重复。现在我们只需要说明边的正确性即可。若对于一个类的所有子串，我们都在它们后面添加一个相同的字符，则得到的所有新的字符串必定都属于另一个相同的类（想想是不是这样）。因此边存在正确性。所以后缀自动机存在。（这里的解释还是不够严谨，如果需要严谨解释可以用类似数学归纳法的方法结合程序说明。因为程序是递推的，初始状态的后缀自动机满足条件，程序正确，所以加入一个新的字符后的后缀自动机也满足条件。这里如果看不懂，可以看完第三节后再尝试理解）

另外，得到点的数量级还不够。下面再证一个比较重要的结论：

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

考虑对于一个后缀自动机：先求出其任意一个生成树，舍弃其其它边。我们知道，后缀自动机上有若干个终止节点。于是我们便从每个终止节点往回跑（倒序跑边与字符），对于每个终止节点跑遍所有属于它（这个类）的子串（从终止节点跑其实就是跑原串的后缀）。注意这里的往回跑是指：对于一个子串，按照原本后缀自动机到达其的唯一路径经过的边往回跑，而非见到代表与现在回到的的那一位字符一样的字符的边就往回跑（因为可能有多条代表相同字符的边指向同一个节点）。对于每个终止节点：我们按一定顺序跑遍属于它的子串。首先跑第一个子串。如果能顺利跑回源点，则跑下一个子串。否则，我们连上本应该跑回的这条边，并沿着它跑到下一个节点。此时，从这个节点出发，一定有一条或多条路径（经过现存的边）回到源点（因为有树的基础结构），则我们往回跑其中任意一条路径。这样，我们实际走的路径形成的字符串不一定是我们原本希望跑的子串，但是，因为加了一条新边，且是从同样的终止节点开始往回跑的，所以得到的字符串必然是属于此类的一个原串后缀，并且肯定是我们之前没有跑过的。这时，我们只需要将这个字符串在将来要跑的那些子串中划掉，然后重跑我们原本希望跑的子串。这样不断重复，直到真正顺利跑完这个子串。然后我们跑下一个子串。当然，如果这个子串已经被划掉了，我们就再下一个。这样，当跑完一个终止节点时，在原本的生成树上增加的边不会超过这个节点的类包含的子串的个数。于是，对于所有终止节点，它们总共使生成树增加的边数不会超过后缀的个数，即n个。而此时，增加了边的后缀自动机已经完整了，因为原串的每一个后缀都在当前的图中被跑出来过了。于是，生成树的边数加n，数量级为O(n)。（看不懂的同学还是可以去看clj的ppt……）

为了方便理解以上内容，我们再画图讲解一下。

以上是原串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里的边意义相近。

现在，我们来研究ans里的东西了。首先看第一行。las是什么？是未加入此字符前最长的前缀（整个串）所属的节点的编号。那么tot呢？是当前后缀自动机节点的总数。

void add(int c)
{
    int p=las;int np=las=++tot;
    dian[np].len=dian[p].len+1;

新加入了一位字符c（减了'a'是为了方便塞进边里，可类比trie里对字符的处理）。我们设未加入c前的原串为旧串，加入c后的原串为新串。显然，此时新串的最长前缀（整个串）所属的节点显然不在原图中（因为原来的所有endpos都不可能包含这一位）。而旧串的最长前缀就变成了新串的次大前缀。所以我们用p记录新串次大前缀（原串的最大前缀）所属的节点，然后新建一个节点np（tot加一），存新的最大前缀所属的类。而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，如果它没有c边（即''longest(p)+c''非旧串子串），那么引一条新边到np。这里用上面的思想解释，即将所有的是旧串后缀且在其后面加c形成的新字符串不是旧串子串的后缀往新串的最大后缀所属节点连一条c边。这样的做法显然是正确的，因为这些后缀加了c产生的新字符串不是旧串的子串，但是因为是旧串的后缀，加上c后必然能在新串最右端出现一次，所以它们也只能在右端点为新串加入字符c的位置出现一次。那么这些新字符串的endpos为\{n\}（还记得是什么吗？原串（这里指新串）的长度）），等同于新串最长前缀的endpos。因此向np连边是正确的。

注意循环的终止条件。如果长度再短，这些旧串后缀加c形成的新字符串就已经在旧串里出现过了，显然与新串最长前缀的endpos不同，所以此时要跳出，进行别的处理。

if(!p)dian[np].fa=1;//以上为case 1

如果已经遍历完了旧串的后缀且它们加c一个都不是旧串的子串（它们在新串中的endpos都是\{n\}），就说明我们已经处理完了新串的所有后缀，完成了任务。所以np的fa直接设为1，表示第一个与新串最长前缀endpos不同且为新串最长前缀的后缀的字符串是空串。程序到此可以结束。（也可这样理解：一个节点跳fa一定可以跳到1，那么连1都没有c的边，说明c根本不是旧串的子串，那就直接把fa(np)设成1即可）

else
{
    int q=dian[p].ch[c];
    if(dian[q].len==dian[p].len+1)dian[np].fa=q;