后缀自动机

发表于 更新于 分类于 本文字数： 3294 阅读时长 ≈ 8 分钟

后缀自动机(SAM)。

简介

后缀自动机，是一个能够解决许多字符串相关问题的，十分强力的数据结构。
其存储的是一个字符串的所有子串。
不要被博客的链接迷惑了，后缀自动机是 Suffix Automaton 。
（博客标题来自俄语 Суффиксный автомат -> Suffiksneyy avtomat）

定义

  1. 后缀自动机是一个DAG。其中的节点叫做状态，边叫做转移。
  2. 图中包含一个初始节点 $t_0$ ，任何节点都可以由之经过一系列的转移到达。
  3. 每一个转移都标有一个字母，且从某一个节点出发的每一个转移都是不同的。
  4. 自动机存在多个终止状态。如果我们从初始状态 $t_0$ 出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串 $s$ 的一个后缀。 $s$ 的每个后缀均可用一条从 $t_0$ 到某个终止状态的路径构成。
  5. 在所有满足上述条件的自动机中，后缀自动机的结点数是最少的。

子串

一个字符串的后缀自动机包含关于这个字符串子串的所有信息。
更准确地来说，对于任意从初始节点 $t_0$ 开始的路径，我们将其转移边上的字符拿下来按顺序排列，都可以得到原字符串的一个子串。
这里需要注意：一条路径对应一个子串，但是一个子串不一定只对应一条路径。

性质

结束位置 endpos 及其等价类

对于字符串 $s$ 的一个子串 $t$ ，我们记其在字符串 $s$ 中的所有结束位置为 $\operatorname{endpos}(t)$ 。例如对于字符串 $aabbabd$ ，我们有 $\operatorname{endpos}(ab)=\{ 2,4 \} $。
两个子串 $t_1$ 与 $t_2$ 的endpos集合可能相等。这样，所有字符串 $s$ 的非空子串都可以根据其endpos集合分为若干等价类。
后缀自动机中的每个状态都会对应一个等价类。

基于endpos，我们可以得到一系列重要结论：

引理1： 考虑两个非空子串 $u$ 与 $v$ （仍然假设 $|u| \leq |v|$ ）。两者的endpos满足这样的一个关系：
$$
\begin{cases}
\operatorname{endpos}(v) \subseteq \operatorname{endpos}(u) & \text{if } u \text{ is a suffix of } v\\
\operatorname{endpos}(v) \cap \operatorname{endpos}(u) = \varnothing & \text{otherwise}
\end{cases}
$$

证明：如果 $\operatorname{endpos}(u) \cap \operatorname{endpos}(v) \neq \varnothing$ ，那么结合我们刚刚证明完的引理1，我们可以知道 $u$ 是 $v$ 的一个后缀。既然 $u$ 是 $v$ 的一个后缀了，那么对于所有 $v$ 出现的地方， $u$ 也会出现，即 $\operatorname{endpos}(u) \subseteq \operatorname{endpos}(v)$ 。而如果 $u$ 的长度小于 $v$ 且 $u$ 还不是 $v$ 的后缀，那么 $v$ 出现的地方 $u$ 一定不会出现，即 $\operatorname{endpos}(u) \cap \operatorname{endpos}(v) = \varnothing$ 。

引理2: 对于任意一个endpos等价类（或者一个状态），其包含的子串集合是最长子串的连续后缀。

证明：我们考虑等价类中两个子串：最长的，记为 $u$ ；最短的，记为 $v$ 。如果 $u=v$ 那么显然不用证明。如果不是，那么对于长度在区间 $[|u|,|v|]$ 内的子串，必定存在子串有 $v$ 为后缀且同时为 $u$ 的后缀。

根据引理3，我们可以知道对于任意状态，其中包含的字串都是其中最长子串的一段连续后缀。这段连续后缀不一定可以覆盖 $[ 1,|\text{最长子串}| ]$ 这一整个区间，但一定是连续的。
我们可以将其看做是不断将最长子串的首个字符删去得到子串的一个过程。

而当我们不断删去，直到删去最短子串的首个字符的时候，我们会发现我们已经离开了这个状态。
我们可以根据这样一个走向创建一系列的新边。
这些新边就被称为link边，也叫做后缀链接。
有些地方也叫fa/father边。

引理4： 所有后缀链接构成一棵根节点为 $t_0$ 的树。

证明：根据后缀链接的定义及引理3，我们可以看出，当前状态的后缀链接到达的是严格更短的字符串。而沿着后缀链接走，最后总能到达代表着空字符串的 $t_0$ 。

我们将后缀链接与endpos关联一下。
根据引理2，我们可以得出，两个endpos等价类不是互相包含，就是互不相交。根据这个包含关系，我们可以列出一棵endpos等价类的树。
对应在后缀自动机上就是对状态建树。

引理5： 通过 $\operatorname{endpos}$ 集合构造的树（每个子节点的子集都包含在父节点的子集中）与通过后缀链接构造的树相同。

证明：是树的证明上面有了，我们看一下对于两者相同的证明。
考虑任意非 $t_0$ 的状态 $u$ 及其后缀链接 $\operatorname{link}(u)$ 。根据引理2和后缀链接的定义，我们可以知道 $\operatorname{endpos}(u) \varsubsetneqq \operatorname{endpos}(\operatorname{link}(u))$ 。这样，我们在建树的时候，就会在 $u$ 与 $\operatorname{link}(u)$ 之间连一条边。

构建

下面是对字符串 $aabbabcd$ 构建后缀自动机得到的结果。
其中，蓝色(#1453AD)的边代表的是转移，绿色(#14AD53)的边代表的是后缀链接。
蓝色(#1453AD)的点代表状态，紫色(#AD1453)的点代表终止状态。

SAM

算法

构建后缀自动机的算法是个在线算法。我们逐个加入字符串中的每个字符，并在每一步中相应地维护刚刚得到的后缀自动机。
为了保证线性的空间复杂度，我们只保存len与link的值。终止状态的值可以在构建完自动机之后求出。

在最开始，整个后缀自动机只会包含一个节点： $t_0$ ，编号为0。我们指定len[0] = 0，link[0] = -1。这里的$-1$表示的是一个虚拟的状态。
然后我们就可以向后缀自动机内添加字符了。

我们向后缀自动机内添加一个字符 $c$ 的算法流程如下：

我们令last为先前对应整个字符串的状态（一开始我们设last = 0）。

创建一个新的状态cur，并使len[cur] = len[last] + 1。

从状态last开始，不断遍历后缀链接。
如果还没有到字符 $c$ 的转移，我们就添加一个指向cur的转移。
如果在某个点已经存在到字符 $c$ 的转移，我们就停下来，并将这个状态记为p。
如果没有找到这样的状态p，我们最终会到达虚拟状态$-1$，这时我们使link[cur] = 0并退出。

如果我们找到了一个状态p，其可以通过字符 $c$ 转移，我们将这样转移到的状态标记为q。
现在我们考虑我们找到的q是否满足len[p] + 1 = len[q]这个条件。

如果满足，那么我们就只需要使link[cur] = q并退出。

如果不满足，那么情况就会变得复杂。
我们需要复制一个状态q，标记为nq。nq将会获得q除了len以外的所有信息。我们将len[nq]赋值为len[p] + 1。之后，我们使link[cur] = link[q] = nq。
之后，使用后缀链接从p往回走，并把沿途所有指向q的转移重定向至nq。

最后，我们将last的值更新为cur。

寻找终止状态

如果我们还想要知道哪些状态是终止状态而那些不是，我们可以在构建完 $s$ 对应的后缀自动机之后再进行寻找。

我们从刚才最后一步得到的last处开始遍历后缀链接，直到最终到达初始节点。
我们将沿途的所有状态都标记为终止状态，因为他们存储着原字符串 $s$ 的至少一个后缀。

类比

在课上听到了一个将后缀Trie和SAM进行类比的点子。
其核心思想就是通过压缩后缀Trie，使得其变成SAM的样子。

代码

洛谷板子题代码：Luogu P3804

应用

见OIwiki。