「后缀自动机」学习笔记

从前啊有个字符串。
从前啊有个沙茶想把这个字符串的所有后缀放到一起。
于是我想到了后缀数组 Trie。

What does SAM do?

把这个字符串的所有后缀插入 Trie，可以发现一个重要的性质：这个 Trie 上根结点到任意结点的任意路径能且仅能表示原串的所有子串。
满足了这个性质，就可以做一些有趣的事情：在原串中匹配模式串、求本质不同子串个数之类的。

然鹅这个东西点数是 O(n2) 级别的完全没有应用价值……
不过，由于都是原串的后缀，而且后缀之间又有后缀关系，所以 Trie 上有些部分是可以合并的。

比如对于字符串 ababa，暴力地构造出 Trie 长这样：

但是显然可以合并成这样：

蓝色代表终止结点。

Some Definitons

让我们定义 endpos(s) 表示 s 作为原串（后称 S）的子串出现的所有位置的右端点之集合。
例如对于 S=ababa,endpos(ab)={2,4}。

接下来有几个引理。

Lemma I

对于原串的两个子串 u,v(|u|≥|v|)，若 endpos(u)⊆endpos(v)，v 是 u 的后缀。

正确性显然（不想证明）。

Lemma II

对于原串的两个子串 u,v(|u|≥|v|)，肯定满足 endpos(u)⊆endpos(v) 或 endpos(u)⋂endpos(v)=∅。

证明类似 Lemma I，也很显然。

Lemma III

对于一个 endpos 等价类，其包含的字符串的长度是连续的。

endpos 等价类：endpos 相同的子串构成的集合。

依然很显然。

Lemma IV

等价类的个数是 O(n) 级别的。

这个引理很重要（可能已经不算是引理了）。

对于一个等价类 v，设其中最长的字符串为 longest(v)。
在 longest(v) 的开头添加一个字符，显然它并不属于该等价类。
并且在 longest(v) 的开头添加一个字符的 endpos 和在 longest(v) 的开头添加另一个不同的字符的 endpos 显然是不相交的（根据 Lemma II）。
于是在 longest(v) 的开头添加字符相当于把它的 endpos 进行分割。

所以等价类之间以这样的分割操作构成一棵树。
一个集合分割的次数不会超过其大小，所以该命题得证。

然鹅真正重要的不是引理本身而是这棵树。
我们称其为 Parent Tree。

Lemma V

对于等价类 v，|longest(fav)|+1=|shortest(v)|。

其中 shortest 的定义与 longest 类似，fav 表示 v 在 Parent Tree 上的父亲。

这个命题同样显然。
在上一个命题的证明过程中已经阐述了这棵树的构成方法——在开头添加字符。

因此我们没必要存储 shortest(v)，可以由 fa 推出。
后文中设 lenv=|longest(v)|。

然后呢，毫无征兆地，我们发现了一个东西：
——SAM 和 Parent Tree 的结点可以共用。

Lemma VI

SAM 的边数也是 O(n) 级别的。

首先考虑 SAM 的一个生成树，此时边数是 n−1=O(n) 的。

对于每个终止结点，我们按某种顺序遍历属于它这个等价类的子串。
如果能遍历回到根结点（源点），则继续遍历下一个子串，否则补边。
此时必定有路径能回到源点，于是随便走一条。

尽管有可能得到非期望的子串，但是因为已经补了边，所以得到的子串依然是属于该等价类的。
以后遍历这个子串的时候直接跳过即可。

然后重新遍历本来期望之中的子串，直到真正遍历结束。

容易发现补的边不超过其 endpos 的大小。

How to build it?

SAM 的构造是一个在线的过程，依次在字符串的最后加入字符并更新 SAM 的形态。

算法的流程是这样的： 1. 设 whole 表示在加入新的字符 x 之前，整个字符串对应的结点。 2. 创建新的结点 p，令 lenp←lenwhole+1。 3. 在 Parent Tree 上，从 whole 往根走，如果走到的结点没有字符 x 的边就给这个结点和 p 连一条 x 的边。 4. 如果走到根了，走过的结点都没有 x 的边，令 fap 改为源点。 5. 否则，设这个结点为 cur，其 x 的边通向点 q。 6. 若 lencur+1=lenq，令 fap←q。
7. 否则，新建结点 nxt，nxt 继承 q 的所有边和 faq。 8. 令 lennxt←lencur+1,fap=faq=nxt。 9. 并且更新原本连 x 边到 q 的点，改为连向 nxt。 10. 最后，更新 whole←p。

现在我们来讨论这个算法的正确性。
前三步都很好理解，直接看第四步。

都没有 x 的边，代表 x 在原串中没有出现过，直接把 fa 连向源点即可。

对于第六步，也就是说 q 刚好对应新串的一个后缀，所以 p 相当于在 q 前面添加若干字符的结果。
并且由于它是第一个被找到的，所以不需要接着往根更新。

然鹅最难理解的部分正是第七八九步。
不满足这个条件，说明 q 的等价类里有奇怪的东西不符合要求的东西。
可以考虑把新串后缀和其他的分开。

所以考虑新建一个结点，把这些东西拆出来。
新建了结点，就得考虑它的信息。

首先考虑连边，直接用 q 的边，显然正确。
然后考虑 len，发现直接改成 lencur+1 就好了。
最后考虑 fa，其实也很显然（我才不说是我懒得写呢

第九步，也就是类似地更新一下出边。

Applications

I.匹配模式串

SA 的话直接二分就好了，不过 SAM 时间更优：从源点开始，类似 Trie 的方式查找子串。

II.不同子串个数

由于 SAM 上没有重复字符串，所以可以 DAG 上 DP。
问题转化为统计 DAG 从根开始的路径条数。

fi=1+∑(i,v)∈Efv

答案即 f1−1。

可以记忆化搜索实现。

III.所有不同子串的长度之和

类似地，同时设 fi 表示以 i 开头的子串个数，gi 表示以 i 开头的子串长度之和。

gi=∑(i,v)∈Efv+gv

加 fv 是因为增加了 v 这个字符。

IV.第 K 小子串——「TJOI2015」弦论

这题有两种情况，其实是类似的。

这个问题相当于，求 SAM 上的字典序 k 小路径。
类比其他数据结构求解第 k 大，我们可以对每个结点记录一个 sum 代表往这个结点走可以得到的路径数量。
然后对于每个结点，依次尝试走 a∼v，直到不够走才往下。
往下时要减去新结点单独的贡献。
直到 k 被减成负数为止。

然后来讨论两种情况。

1. 忽略相同子串的重复贡献。
   直接把每个结点的贡献当做 1 来做（除了根节点）。
   然后 DAG 上 DP 计算 sum。

2. 计算相同子串的重复贡献。
   考虑怎么算出每个结点实际的贡献。
   可以在 Parent Tree 上 DP 求 |endpos|，这个其实是个套路。

代码见 https://www.alpha1022.me/articles/loj-2102.htm

V.动态不同子串个数——「SDOI2016」生成魔咒

由于后缀自动机的构造本来就是一个在线的过程，所以我们可以考虑每次往答案中添加新的贡献。

又根据后缀自动机的定义，不同子串的个数其实就是 tot∑i=1(leni−lenfai)。
所以我们再每次添加字符的时候更新答案即可。

这题如果用 SA 来做的话会很麻烦，但是 SAM 就很简洁了。

代码见 https://www.alpha1022.me/articles/loj-2033.htm