老年人重学算法系列 #1 SAM 是怎么被构造的？

· · 个人记录

本文在 2026/5/13 完成重构，重构结果可以在 https://tiger2005.top/posts/sam/ 中看到。

前言

众所周知，我是 OI 老年人；众所周知，我还要被 ACM 继续折磨四年，但是我已经把大多数高妙算法的细节忘了。

于是我打算寻找一种更加直观的方式重新理解一些高妙算法，在加深我自己对算法的充分理解的同时，也希望可以给一些算法竞赛爱好者带来帮助。这个系列也就这么产生了（虽然完全不知道会不会这一期之后就没了）。

今天尝试以一种很新的角度看待后缀自动机、后缀链接树和结束位置集合。我尽量保持在 OI Wiki 中对各个名词的定义，方便后面对其他博客和介绍的理解，同时也会引入一些创新（确信）的名词辅助理解。

本文刻意绕开了反复的数学理论证明，而尝试通过直观的角度对算法进行描述。如果你已经对 SAM 存在自己的了解，建议就不要再被这篇文章扰乱思想了（

一些定义

为了方便，我们先定义字符串的下标 从 1 开始，并且对于一个长度为 n 的字符串 s，定义 s[0] = s[n+1] = \epsilon，代表此处字符为空。

自动机是什么

如果你对 Trie 的结构有一定了解，而且并不想接触到诸如“DFA 最小化”的陌生名词的话，这一个部分可以跳过。

后缀自动机属于 DFA 的一种。简单而言，DFA 包含了一些点，以及这些点在遇到一个字符之后转移到的点（可能不能转移）。在开始运作时，我们站在起始点上，每次根据一个字符跳转到一个新的点（也有可能没有可以到达的点，此时称作失配）。DFA 还存在一些终止点，当我们以 str 为操作序列，从起始点成功跳到一个终止点的时候，则视为成功匹配 str。

为了匹配一个字符串 s 的所有后缀，我们考虑将它的后缀全部加入到一个 Trie 中，然后将这个 Trie 视为一个 DFA，起始点在根节点，插入完毕后停留的节点设置为结束点即可。对于一个子串 s[l...r]，在匹配的时候就可以顺着 s[l...n] 这个后缀往下走，走到 r-l+1 步停下来的时候就会恰好在这个后缀代表的树链中，也就成功匹配了。对于非子串，显然会在一个时刻无法转移，也就导致了失配。

显然，这个方法在最坏空间复杂度和构建的时间复杂度上都是无法接受的。在自动机相关算法中，存在一种最小化 DFA 的算法。简单来说，对于 DFA 上的两个点，如果在接收到 \Sigma 中任意一个字符的时候，都会跳转到相同的点（或者同时失配），那么可以认为两个点不可区分，也就可以进行合并了。

我们考虑在前面的暴力构建过程中，对每个点定义“终止位置集合”，并且考虑插入 s[x...n] 时，在接收 s[i] 状态转移（或者开辟）一个点的时候，将这个点的终止位置集合插入 i，表示这个点可以借助 s[x...i] 这一操作序列从起始点到达。然后考虑对这个 Trie 树进行 DFA 最小化，每次合并两个不可区分的点时，也将这两个点的“终止位置集合”进行合并。

本文介绍的后缀自动机算法，旨在直接构造出这个最小化后的 DFA，其中利用到了“终止位置集合”，以及描述其包含关系的后缀链接。我在此不会展开对“构造出的 DFA 必然是状态两两不可区分的 DFA”命题的证明，感兴趣的可以直接读论文或者自行推敲（相信我，没那么难）。

延长、矛盾、抉择

考虑定义 \operatorname{endpos}(t)。我们假设 t 在 s 中总共出现 k 次，分别为 s[l_i...r_i]\ (i \in [1,k])，那么 \operatorname{endpos}(t) = \cup_{i=1}^{k}\{r_i\}。特别的，定义 \operatorname{endpos}(\texttt{""}) 为一个足够大的整数集（为了方便叙述，不妨设为 \cup_{i=0}^{n}\{i\}）。

定义在长度 len 下，一个位置 x\ (x \geq len) 的 目标字符 为 s[x - len]。这一个字符象征着我们尝试将 通过长度为 len 的字符串得到的 \operatorname{endpos} 进行 延长，使得长度变为 len + 1 时，\operatorname{endpos} 中每一个位置等待匹配的字符。需要注意的是，目标字符也可能是 \epsilon。

举个例子。对于 s = \texttt{abcbc}，t = \texttt{bc} 的情况，可以知道 \operatorname{endpos}(t) = \{3,5\}。那么为了将长度从 2 延长到 3，有：

首先观察到一个事实：向 t 的最前面追加一个字符 c，等价于更加严格地限定了 \operatorname{endpos} 的需求。在 \operatorname{endpos}(t) 中，有且只有目标字符为 c 的位置会进入到 \operatorname{endpos}(c + t) 中。故可以得到 \operatorname{endpos}(c + t) \subseteq \operatorname{endpos}(t)。根据归纳法，我们同时得到事实：

\operatorname{endpos}(t' + t) \subseteq \operatorname{endpos}(t)

由于对一个字符串前面追加一个字符可能会使得 \operatorname{endpos} 集合减小，我们考虑在实际中，何时会发生减小的情况。

对于一个可被构造的 \operatorname{endpos} 集合 S（也就是存在一个字符串 t，使得 \operatorname{endpos}(t) = S，下面定义能够构造出集合 S 的字符串为 构造串），根据前面的事实，我们可以找到一个长度区间 [L, R]，使得所有构造串 t 符合以下性质：

上述性质都可以进行感性证明。注意到一个前提：随着延长的进行，\operatorname{endpos} 大小单调不升。首先，由于 S 是可被构造的，我们随意选择 S 中的一个位置 p，并慢慢将长度 len 从 0 开始 延长；在此过程中，\operatorname{endpos}(s[p-len+1, p]) 将会从足够大的整数集慢慢减少，在某个时刻必然会等于 S（根据定义，必然会在 s[1...p] 中存在一个符合情况的后缀）。此时我们找到了 L 的值。然后我们考虑继续 延长，直到 \operatorname{endpos}(s[p-len, p]) \neq S，我们就找到了 R 的值。

在此过程中，所有 len 都是符合条件的，而且每次延长都是将子串位置的左端点左移一位，等价于在前面加上一个字符。于是我们证明了前两点，同时也就得到了第三点。

当我们尝试从 R 延长到 R+1 时，我们发现无法再将 \operatorname{endpos} 维持为 S。此时我们设这个长度对应的子串为 t_0，并尝试描述在其开头加入字符时的行为。

考虑其内所有位置在长度为 R 时的 目标字符，如果所有的目标字符都一样，那么显然可以统一进行延长，而不改变 \operatorname{endpos} 本身。因此我们得到：这些位置的目标字符并不唯一，我们称之为在长度为 R 时产生 矛盾。

此时考虑：如果选择其中一个字符 c，那么有且只有所有符合“目标字符为 c ”的位置符合这个新增的限制，并作为 \operatorname{endpos}(c + t_0) 的一个元素。对于这种选择一个字符，并将原先集合取出一部分作为新的 \operatorname{endpos} 的行为，我们不妨称为 抉择。

不难发现，由于每个位置的目标字符唯一，那么每个位置只会出现在至多一个抉择形成的新 \operatorname{endpos} 中。与此同时，由于可能出现至多一个位置，其目标字符为 \epsilon，而显然我们不希望字符串中包含 \epsilon，故我们不对这个字符定义抉择，这个位置也将成为唯一一个不出现在任何抉择后集合中的位置。

那么接下来，我们就可以重新看待 \operatorname{endpos} 的变换过程了。

\operatorname{endpos} 的相关性质

方便起见，我们定义 \operatorname{minlen}(v) 和 \operatorname{len}(v)，代表一个可被构造的集合 v 对应的字符串长度的最小值和最大值（和前面的 L 和 R 等价）。

接下来有几个定理，它们现在都可以得到很简单的证明：

定理 1：对于从可被构造的集合 V 仅通过一步抉择得到的非空集合 v，存在：\operatorname{minlen}(v) = \operatorname{len}(V) + 1。

证明：为了从 V 中进行抉择，我们需要在 V 对应的最长构造串的最前面加上当前抉择的字符，而此时得到的显然是 v 的最小构造串，因此可以得到上式。

定理 2：对于一个子串 s[l...r]，它的 \operatorname{endpos} 必然会等于上述构造中的一个小集合。

证明：我们从最开始的整数集开始，每次抉择只选择包含 r 的位置往下走，并且限制延长和抉择后的长度最多只能到 r-l+1。考虑到 r 可能会在中途被移出，但是这种情况只会在 r 位置的目标字符为 \epsilon 时发生，此时 len = r \geq r- l + 1，由于一次抉择会使得长度增加 1，故必然不会进行这一个抉择。

定理 2 确定了这个变换过程的正确性。

后缀链接 \operatorname{link} & 后缀链接树

接下来，我们考虑将变换过程中得到的每一个集合看作一些状态（也可以认为是一些点），分别为 v_0, v_1, \cdots, v_{N}。同时，下面对单独的一个状态（或者集合）考虑时，统一计为 v。同时，v_0 被定义为 \operatorname{endpos}(\texttt{""})，也就是初始的集合。

随后，我们假设在对状态 v_i 进行抉择的时候，得到的其中一个新状态为 v_j，那么定义 \operatorname{link}(v_j) = v_i。\operatorname{link}(v_0) 不重要。

考虑 \operatorname{link}(v) 的实际含义，实际上代表了 v 的任意一个构造串在从开头不断移出字符的过程中，第一次发生 \operatorname{endpos} 集合变化时对应的状态，那么可以认为 \operatorname{link}(v) 等价于 v 的任意一个标识串中最长的、\operatorname{endpos} 集合不等于自身状态的后缀对应的状态。

考虑从 \operatorname{link}(v_i) 向 v_i 连边，根据整个转换过程，最后所有边将会构建出一棵“后缀链接树”。其中对于 f \to v 的连边，根据定理 1 有 \operatorname{minlen}(v) = \operatorname{len}(f) + 1。同时，一个点的所有儿子代表了每一种抉择产生的新状态。

接下来又是两个定理：

定理 3：对于两个状态，它们对应的集合要么存在包含关系，要么交集为空。

证明：对于后缀链接树上的两个状态：

定理 4：对于一个长度为 n\ (n \geq 2) 的字符串，其状态数不会超过 2n-1。

证明：OI Wiki 在这个定理上给出的第二个证明并不是很严谨。

考虑对于一个非叶子节点对应的状态，如果这个状态在抉择的时候扔掉了一个点 p，那么将状态 \{p\} 追加到这个节点的儿子中。

重新观察这棵树，我们会发现这棵树的叶节点有 n + 1 个，且分别只包含了 [0,n] 中整数的一个（它们分别代表了每个元素被移出的位置）。同时，每个非叶子节点都会包含至少两个儿子，故理论上点个数不会超过 2n+1。

考虑抠出多余的两个点。\{0\} 显然是新加入的状态，所以可以直接减去。然后我们考虑 \{1\}：

于是我们成功证明了：原先树上的节点个数不会超过 2n-1，等价于待证命题。

SAM 的特性

SAM 维护的状态就是上一节开头提到的所有状态。在维护了后缀链接树的同时，SAM 也需要完成它的本质工作——为每个点准备好它的转移方向。根据前面对 DFA 行为的定义，对于一个点的所有构造串 str，需要满足：从起始点开始，以 str 作为操作序列进行转移，应当恰好能到达这个点。

同时，SAM 上的每一个转移都具有 松弛性。对于转移 p \to q，除了将 p 中每个元素加上 1 之外，我们也会从中去除一部分元素，这导致 q 对应的构造串长度拥有更加宽松的限制。从数学上来说，[\operatorname{minlen}(p) + 1, \operatorname{len}(p) + 1] 被完全包含于 [\operatorname{minlen}(q), \operatorname{len}(q)] 区间中。

我们假设我们已经构造好了长度为 n 的字符串 s 对应的 SAM，接下来希望动态维护 s + c 的答案。为了方便介绍并证明接下来的增量构造法，请允许我在下面提出一些新的概念。

下面是一个比较简单的命题。

命题 1：所有状态中必然存在状态 \{n\}。

证明：根据定理 2，任何一个子串都可以通过指定方向的游走实现，我们同样运用在这里，在抉择的时候只选择包含 n 的集合走。考虑我们最后到达的叶节点对应的状态 last。根据定理 2 的描述，元素 n 只会在 \operatorname{len}(v) = n 对应的状态下被移走，因此可以得到 \operatorname{len}(last) = n。与此同时，这个字符串中也只能以 n 为右端点形成长度为 n 的子串，故 last = \{n\}。

此时，我们添加 边缘链 的概念，代表从 last 状态跟随后缀链接向上走形成的树链。

然后我们尝试考察边缘链上的点通过 c 字符进行转移后，分别会到达哪里。接下来我们引入下一个命题。

命题 2：边缘链上的点通过 c 字符转移后，除了最后若干个点可能失配之外，其余点的匹配均对应一个后缀链接树上的链，并且深度之间存在不严格偏序。

证明：我们引入 匹配潜能 的概念。对于一个位置 pos，其具有 c - 匹配潜能 当且仅当 s[pos+1]=c。下面将 c - 匹配潜能 简称为 c - 潜能。

不难发现，对于一个状态 v，不妨假设其在接收 c 字符后转移到 w，那么 w 可以通过以下方式构造：

注意到对所有集合的元素加上 1 并不会影响转移后状态之间的包含关系，所以我们直接考察边缘链上的状态在经过第一部操作后的包含情况。

假设存在树边 u \to v，有 v \subsetneq u，而当我们移出两者中不具有 c - 潜能的元素后（等价于对固定集合的补集），不难发现满足 v' \subseteq u'。进行进一步分分析：

于是，除了最后一些没能转移的点之外，其余点的转移的确会形成一个已有的树链，不妨定义为 转移链。

这里可能会凭空出现一张边缘链和转移链的示意图。

我们不妨考虑，在增量的过程中，会有哪些点代表的 \operatorname{endpos} 集合发生了变化。不妨考虑在 s 后面插入字符 c 的时候，具体什么发生了改变。我们注意到：n 位置获得了 c - 潜能，同时 n+1 也将有可能出现在已有的一些状态中。我们分别分析这两个变化。

因此我们只需要关注在边缘链和转移链上发生的变化即可，其他点在理论上并不会受到本次增量的过多影响（需要在算法过程中进行精细处理，这是后话）。

算法

根据上面的分析，我们的目标也就很明确了：找出在边缘链上可能出现改变的转移，并且适度调整转移链，使其成为下一次增量的边缘链。我们接下来对算法的详细步骤进行分析。

第一步

我们考虑边缘链最后那些没有 c 字符对应转移的点。这些点曾经都不包含具有 c - 潜能的位置，而在这次增量后，有且仅有 n 这个位置具有 c - 潜能，可以通过 c 字符进行转移。据此，我们断言这些点在本次增量中获得了一个转移，接收 c 字符并转到 \{n+1\} 这一状态上。

在具体实现上，我们需要新开一个点表示这个状态，将这个点的 \operatorname{len} 值设为 n+1，并且从 last 往上走，将所有这样的点添加转移。我们持续这个循环，然后到达第一个存在 c 转移的点，或者直到到达根节点都没有找到这样的点。

第二步

如果我们找到根节点都没能找到存在 c 转移的点，说明此时转移链是并没有存在的。但是注意到，随着字符串的加强，根节点状态集合将会直接加入 n+1 这个元素，故理论上根节点是我们能够找到的、唯一一个包含 n+1 的状态了，此时直接将 \{n+1\} 视为根节点的儿子即可。

第三步

否则，我们找到了一个节点 p，其存在一个转移，接收 c 字符并转移到节点 q。显然，此时我们找到了转移链的底端。

根据分析，随着转移链上的点深度越来越小，对应的构造串长度也就越短，限制也就相对越少，n+1 也就越有可能进入到这个状态。所以我们可以断言：在转移链上，n+1 将会从某一个长度开始进入到链上的某一个点（这个长度可能刚好踩着一个点的构造串长度区间之间，所以我们可能需要将这个点分裂开），然后从这个点开始向上传递，在所有祖先中出现。

找到 n+1 进入转移链的点大概是比较困难的，不过可喜的是，这个点恰好就是 q。接下来会对这个命题进行证明。

我们不妨假设 p 在边缘链中的儿子是 r。那么在 r 转移到 p 的时候，p 对应的集合也比 r 对应的集合多了一些点，而其中就包含了 r 中并不存在的、具有 c - 潜能的点（因为存在 c 对应的转移当且仅当存在具有 c - 潜能的点）。我们设这些具有 c - 潜能的点形成的集合为 S，根据抉择的性质，S 中所有点所属的抉择方向必然不指向 r，否则 r 中就会存在具有 c - 潜能的点，和条件不符。

既然 S 包括了 p 中至少一类抉择方向，那么在加入 n 之后，对应的抉择方向也会变为至少两类。根据转移的原理，q 应当由两部分组成：

我们根据上述论证说明了 S \cup \{n\} 在长度为 \operatorname{len}(p) 时存在矛盾，而 q 只是把其中所有的元素加上 1，故对于 q 来说，其必然会在长度为 \operatorname{len}(p) + 1 时产生矛盾。

接下来注意到，根据转移的松弛性，有 \operatorname{len}(q) \geq \operatorname{len}(p) + 1，故 q 处的矛盾和抉择是必然会触发的，我们也就成功证明了这个命题。

我们对 \operatorname{len}(q) 进行判定：

边数和复杂度的正确性

在这个体系下比较难以说明这一点，建议再回头看看 OI Wiki 的说明！