后缀自动机（Suffix Automaton）本质上就是接受字符串集合等于一个给定字符串 \(S\) 后缀集合的最小化 DFA。SAM 可以在 \(O(|S|)\) 的时间内构造出来。

等价关系

在下文中统一设母串为 \(S\)。

定义 1：令 \(\operatorname{endpos}(s)\) 表示子串 \(s\) 在 \(S\) 中的结束位置集合。如 \(S = abcababc, s = ab\)，则 \(\operatorname{endpos}(s) = \{2, 5, 7\}\)。特别地，\(\operatorname{endpos}(\emptyset) = \{1,2,3, \cdots, |S|\}\)。

引理 1：两个子串 \(u, w\) 是 \(\operatorname{endpos}\) 等价的，且假设 \(|u| < |w|\)，则 \(u\) 是 \(w\) 的一个后缀。

证明：脑补一下，不证自明。

引理 2：考虑两个子串 \(u, w\)，假设 \(|u| < |w|\) 则 \(\operatorname{endpos}(u)\) 与 \(\operatorname{endpos}(v)\) 有且仅有以下两种关系：

\(\operatorname{endpos}(w) \subseteq \operatorname{endpos}(u)\)：此时 \(u\) 一定是 \(w\) 的后缀。
\(\operatorname{endpos}(w) \cap \operatorname{endpos}(u) = \emptyset\)：其他。

证明：如果 \(\operatorname{endpos}(w) \cap \operatorname{endpos}(u) \neq \emptyset\)，那么它们至少都会在原串的某一点结束，结合 \(|u| < |w|\)，\(u\) 一定就是 \(w\) 的后缀，如此一来 \(w\) 结束的地方 \(u\) 也一定结束，因此 \(\operatorname{endpos}(w) \subseteq \operatorname{endpos}(u)\)。

引理 3：考虑一个 \(\operatorname{endpos}\) 等价类，如果将其中的串按照长度从小到大排序，则后一个串的长度一定比前一个串的长度严格大 \(1\)，或者说，这个等价类的字符串取遍了某一区间内的所有长度。

证明：记这个等价类当中最短的串为 \(u\)，最长的串为 \(w\)。首先由引理 1，一个等价类必定由 \(w\) 和它的一系列后缀组成。考虑长度在 \(u, w\) 之间的 \(w\) 的任意后缀 \(x\)，因为 \(x\) 是 \(w\) 的后缀，由引理 2，\(\operatorname{endpos}(w) \subseteq \operatorname{endpos}(x)\)，同时又因为 \(u\) 是 \(x\) 的后缀，\(\operatorname{endpos}(x) \subseteq \operatorname{endpos}(u)\)，结合 \(\operatorname{endpos}(w) = \operatorname{endpos}(u)\)，则 \(x\) 与 \(u, w\) 也 \(\operatorname{endpos}\) 等价。

后缀链接

\(\operatorname{endpos}\) 集合描述了一个串在母串当中的出现情况。我们希望构建出来的 DFA 要最小化，因此我们自然希望一个节点表示一整个 \(\operatorname{endpos}\) 的等价类。即 SAM 当中每个节点的 \(\operatorname{endpos}\) 互不相同。

定义 2：对于一个节点 \(v\)，令 \(\operatorname{endpos}(v)\) 表示其表示的 \(\operatorname{endpos}\) 等价类。

我们又知道一个节点表示的字符串是 \(S\) 的某一个前缀的前几个后缀（引理 3）（假设把后缀长度从大到小排序）。

定义 3：既然某个节点 \(v\) 表示某前缀的前几个后缀，令 \(\operatorname{link}(v)\) 表示第一个不在等价类 \(v\) 中的后缀所在的等价类节点，称为 \(v\) 的后缀链接。

定义 4：令 \(\min(v)\) 表示节点 \(v\) 表示的最短子串，\(\max(v)\) 表示节点 \(v\) 表示的最长子串。

观察 1：结合定义 3，显然 \(\left|\min(v)\right| = \left|\max(\operatorname{link}(v))\right| + 1\)。

定义 4：设 SAM 初始节点为 \(v_0\)，令 \(\operatorname{link}(v_0) = \emptyset, \min(v_0) = \max(v_0) = \emptyset\)。

引理 4：节点与后缀链接构成一棵以初始节点 \(v_0\) 为根的树。

证明：后缀链接 \(\operatorname{link}(v)\) 的表示的子串长度是严格小于 \(v\)。顺着后缀链接总可以退回到表示子串长度为 \(0\) 的 \(v_0\)。

观察 2：由引理 2，定义 3，\(\operatorname{endpos}(v) \subsetneq \operatorname{endpos}(\operatorname{link}(v))\)。

观察 3：因此，后缀链接组成的树也完全对应 \(\operatorname{endpos}\) 等价类的子集关系。

构建算法

我们采用增量式的方法构建后缀自动机，即考虑在 \(S\) 的 SAM 的基础上构建 \(S|c\) 的后缀自动机：

在算法中，我们对于一个节点 \(v\) 只存储以下信息：

\(\operatorname{link}(v)\)：后缀链接
\(\operatorname{len}(v) = |\max(v)|\)
转移边

算法流程如下：

令 \(v_{\text{last}}\) 表示原来表示整个 \(S\) 串的节点。
创建新节点 \(v_{\text{cur}}\) 用于表示串 \(S|c\)，令 \(\operatorname{len}(v_{\text{cur}}) = \operatorname{len}(v_{\text{last}}) + 1\)。
从 \(v_{\text{last}}\) 开始顺着后缀链接一路向上，对于没有 \(c\) 转移边的节点添加到 \(v_{\text{cur}}\) 的后缀转移。如果一路到了 \(v_0\)，那么令 \(\operatorname{link}(v_{\text{cur}}) = v_0\)，否则在第一个存在 \(c\) 转移边的节点 \(p\) 出停住。记 \(p\) 顺 \(c\) 转移到 \(q\)。
判断：
1. 如果 \(\operatorname{len}(q) = \operatorname{len}(p) + 1\)，则令 \(\operatorname{link}(v_{\text{cur}}) = q\)。
2. 否则，将 \(q\) 复制一份得到 \(q'\)，令 \(\operatorname{len}(q') = \operatorname{len}(p) + 1\)。令 \(\operatorname{link}(q) = q'\) 且 \(\operatorname{link}(v_{\text{cur}}) = q'\)。同时再顺着 \(p\) 的后缀链接向上，把所有指向 \(q\) 的 \(c\) 转移边重定向到 \(q'\)，直到到达初始节点或者遇到一个非 \(q\) 的转移为止。

正确性证明

首先，算法从创建一个新状态 \(v_{\text{cur}}\) 开始，这个节点表示的字符串是 \(S|c\)，同时也开辟一个新的等价类。

接下来对于之前的后缀我们都要做相应的更新（加上 \(c\) 才算新的后缀），最简单的方法就是给这些节点加上往 \(v_{\text{cur}}\) 的字符 \(c\) 转移边，但是这些转移边必须不与之前的转移冲突才行，因此我们到节点 \(p\) 就停止了，再加就冲突了。（注意我们在这里每给一个节点 \(v\)（设表示串为 \(S_v\)）加一条 \(c\) 转移边，我们就把 \(S_v|c\) 加到了 \(v_{\text{cur}}\) 表示的串集合当中。这决定了 \(v_{\text{cur}}\) 的后缀链接应该链接到哪里。）

首先如果我们找不到节点 \(p\)，也就是我们一路到了初始节点，那说明这个 \(c\) 就根本没有 \(S\) 中出现过，也说明 \(v_{\text{cur}}\) 一下子表示了 \(S|c\) 的所有非空后缀了，因此由后缀链接的定义 \(\operatorname{link}(v_{\text{cur}}) = v_0\)。

如果我们确实在 \(p\) 节点停下了，令 \(p\) 代表的串集为 \(S_p\)，那 \(q\) 的串集 \(S_q\) 至少包含 \(S_p|c\)，而此时 \(S_p|c\) 的 \(\operatorname{endpos}\) 集合是被拓展的（因为现在 \(S_p|c\) 也会在 \(S|c\) 的末尾结束），因此：

如果 \(S_q\) 只包含 \(S_p|c\)，也就是 \(\operatorname{len}(q) = \operatorname{len}(p)+1\) 那么我们可以直接拓展 \(q\) 的等价类。此时 \(\operatorname{link}(v_{\text{cur}}) = q\)。
如果 \(S_q\) 不只包含 \(S_p|c\)，也就是 \(\operatorname{len}(q) > \operatorname{len}(p) + 1\) 的话，那么 \(S_q\) 中只有一部分串的 \(\operatorname{endpos}\) 集合被拓展了，此时我们有必要重新开一个节点来表示拓展得到的新等价类。那些比 \(S_p|c\) 长的，没有拓展的串仍然保留在 \(q\)，\(S_p|c\) 被单独移到了 \(q'\)，由定义那么 \(\operatorname{link}(q) = q'\)。最后我们需要做一些收尾工作，也就是把一些节点从转移到 \(q\) 变成转移到 \(q'\)，我们发现这些节点代表的串一定是 \(S_p\) 的后缀，因此只要一路 \(p\) 的后缀链接向上就行了。

关于时空复杂度，首先这个算法本身的保证了状态数的上界是 \(2|S| - 1 = O(|S|)\) 的。

其次这个算法的转移数也是线性的，这两个性质一起确保了整个算法的均摊复杂度是线性的。具体证明可以看这里。

代码实现

个人认为 SAM 的代码实现只要理解了 SAM 的原理其实是比 SA 简单的：

namespace sam {
    int cnt = 1, last = 1;
    const int EPSILON = 26;
    int len[N], link[N], nxt[N][EPSILON];
    
    void extend(int c) {
        int cur = ++cnt, p = last;
        len[cur] = len[last] + 1;
        for (; p && !nxt[p][c]; p = link[p]) nxt[p][c] = cur;
        if (!p) link[cur] = 1;
        else {
            int q = nxt[p][c];
            if (len[q] == len[p] + 1) link[cur] = q;
            else {
                int nq = ++cnt;
                len[nq] = len[p] + 1;
                link[nq] = link[q];
                copy(nxt[q], nxt[q] + EPSILON, nxt[nq]);
                for (; nxt[p][c] == q; p = link[p]) nxt[p][c] = nq;
                link[q] = link[cur] = nq;
            }
        }
        last = cur;
    }
}

SAM 绝对是代码中 “微言精义” 的典范 233。

其次在 DFS 遍历 SAM 的后缀链接树的时候其实有一个小技巧，就是把节点按照 \(\operatorname{len}\) 从大到小的顺序进行访问（这一步可以桶排），这样可以确保儿子节点一定在父亲节点之前访问到。

后缀自动机笔记

Table of Contents