详解一下后缀自动机

后缀自动机，通常写作 SAM（Suffix Automaton），是字符串算法里非常强的一种数据结构。它看起来叫“后缀”自动机，但实际上它能高效表示 一个串的所有子串。

你可以把它理解成：

用一个很紧凑的有向图，压缩表示某个字符串的全部子串信息。

它常用于这些题：

• 判断一个串是不是原串的子串
• 统计不同子串个数
• 求某个子串出现次数
• 求最长公共子串
• 做字典序相关的子串问题

下面我按“直觉 → 定义 → 构造 → 为什么对 → 常见应用”的顺序讲。

---

1. 它到底是什么

设原串是 S。

后缀自动机是一个 DFA（确定有限自动机），满足：

• 它能接受 S 的所有子串
• 并且在所有能接受这些子串的 DFA 里，它是最小的

这里“最小”不是说代码短，而是 状态数最少。

这很厉害，因为一个长度为 n 的串有 O(n^2) 个子串，但 SAM 只需要 O(n) 个状态和边。

---

2. 先建立直觉：状态表示什么

SAM 的每个状态，不是对应“某一个字符串”，而是对应 一类字符串。

更准确地说，一个状态对应一组 endpos 相同的子串。

什么是 endpos

对于字符串 t，它在 S 中可能出现多次。
endpos(t) 表示 t 在 S 中所有出现位置的“结束下标”集合。

例如 S = "ababa"：

• "a" 出现在位置 1, 3, 5 结束，所以
  endpos("a") = {1, 3, 5}
• "aba" 出现在区间 [1,3] 和 [3,5]，结束位置是 3, 5
  endpos("aba") = {3, 5}

如果两个子串的 endpos 集合一样，它们会被压到同一个状态里。

这就是 SAM 能压缩的根本原因。

---

3. 一个状态里存什么

通常每个状态会维护这几个东西：

len[v]

状态 v 所表示的那一类字符串中，最长串的长度。

link[v]

后缀链接，指向一个状态，表示：

把当前状态对应的最长串，去掉最前面若干字符后，得到的“最长真后缀”所在的状态。

它有点像 KMP 的 fail，也有点像 Trie 的后缀指针，但本质不完全一样。

next[v][c]

从状态 v 出发，读入字符 c 后转移到哪个状态。

---

4. 一个非常关键的性质

对每个状态 v，它其实代表了一段长度区间：

$$(\text{len[link[v]]}+1) \sim \text{len[v]}$$

也就是说，这个状态里对应的字符串长度不是一个，而是一整段连续区间。

例如某状态 v：

• len[v] = 10
• len[link[v]] = 6

那么它表示的字符串长度就是：

$$7, 8, 9, 10$$

并且这些长度对应的字符串，endpos 都相同，所以被归成同一类。

这个性质特别重要，很多计数公式都靠它。

---

5. 为什么叫“后缀自动机”

因为它通常是按原串从左到右逐个加入字符构建的。
每次加入一个字符，都会让“当前整个前缀的所有后缀”得到更新。

换句话说：

• 构造过程围绕“后缀”展开
• 但最终结构表示的是“所有子串”

所以名字里有“后缀”，用途上却覆盖了“子串”。

---

6. SAM 长什么样

如果把状态看成点、转移看成边，那么：

• 沿着某条路径读出的字符串，一定是原串的某个子串
• 原串的每个子串，都能在图上找到一条对应路径

因此：

“子串问题” 经常就变成了 “自动机上走路径的问题”。

---

7. 在线构造：核心思想

SAM 可以在线构造。
每加入一个字符 c，用摊还 O(1) 时间更新，整个构造 O(n)。

构造时最核心的变量是：

• last：表示当前整个串对应的状态

初始只有一个根状态 0：

• len[0] = 0
• link[0] = -1

每次插入字符 c，创建一个新状态 cur，表示“新串的整个前缀”。

---

8. 插入一个字符时到底发生什么

假设当前已经处理了字符串 S，现在加入一个字符 c，得到新串 S+c。

第一步：新建状态 cur

令：

• len[cur] = len[last] + 1

它代表新的整个前缀 S+c。

---

第二步：从旧的后缀链往上跳，补转移

从 p = last 开始：

如果 p 没有字符 c 的转移，就把 next[p][c] = cur，然后 p = link[p] 继续往上跳。

这一步的含义是：

之前那些后缀后面接上 c，现在都能形成新的子串，所以要补边。

直到：

• 跳到 -1，或者
• 遇到某个状态已经有 c 的转移

---

第三步：分情况讨论

假设跳到某个状态 p，它已经有 c 转移，设

$$q = next[p][c]$$

这时分三种情况。

---

9. 三种情况

情况 1：一直跳到根外了

如果 p == -1，说明一路都没找到已有的 c 转移。

那么直接设：

$$link[cur] = 0$$

即新状态的后缀链接指向根。

这很好理解：新串的最长真后缀里，能落到已有状态的就是从根开始那部分。

---

情况 2：找到了 q，而且正好“顺理成章”

如果：

$$len[p] + 1 = len[q]$$

那说明 q 恰好就是我们要找的那个状态，不需要拆分。

直接：

$$link[cur] = q$$

这表示新状态的最长真后缀落在 q。

---

情况 3：找到了 q，但长度不对，需要克隆

如果：

$$len[p] + 1 < len[q]$$

这说明 q 这个状态“太大了”，它混合了两类本该分开的情况。
此时就要创建一个 克隆状态 clone。

设置：

• len[clone] = len[p] + 1
• next[clone] = next[q]
• link[clone] = link[q]

然后把：

• link[q] = clone
• link[cur] = clone

并且沿着后缀链往上，把所有原本指向 q 的那条 c 转移，在符合条件时改成指向 clone。

---

10. 为什么需要 clone

这是 SAM 最难懂、但也是最核心的地方。

一句话解释：

之前的某个状态 q，同时代表了两批字符串；加入新字符后，发现这两批字符串的行为不再一致了，所以必须把它拆开。

而“克隆”就是一种高效的拆分方式：

• 复制 q 的出边
• 缩短它的 len
• 让一部分转移改连到 clone
• 于是原来混在一起的等价类被拆成两个状态

你可以把 clone 理解成：

“把原状态历史上的一部分语义，单独拎出来”

注意：

• clone 不是对应新增前缀
• 它是为了维护最小 DFA 结构而人工制造的状态

---

11. 标准模板代码

这是最常见的 C++ 写法骨架：

cpp
struct SAM {
    static const int ALPHA = 26;

    struct State {
        int len, link;
        int next[ALPHA];
        State() : len(0), link(-1) {
            memset(next, -1, sizeof(next));
        }
    };

    vector<State> st;
    int last;

    SAM(int max_len = 100000) {
        st.reserve(2 * max_len);
        st.push_back(State()); // root
        last = 0;
    }

    void extend(char ch) {
        int c = ch - 'a';
        int cur = (int)st.size();
        st.push_back(State());
        st[cur].len = st[last].len + 1;

        int p = last;
        while (p != -1 && st[p].next[c] == -1) {
            st[p].next[c] = cur;
            p = st[p].link;
        }

        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = (int)st.size();
                st.push_back(st[q]);              // 拷贝 q
                st[clone].len = st[p].len + 1;   // 只改 len

                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }

                st[q].link = st[cur].link = clone;
            }
        }

        last = cur;
    }
};

如果字符集不是 'a'~'z'，把 next 改成 map 或 unordered_map 即可。

---

12. 为什么复杂度是线性的

SAM 有两个经典结论：

状态数最多 2n - 1

长度为 n 的串，SAM 的状态数是线性的。

转移数也是线性的

在定长字符集下，整体也是 O(n) 级别。

因此：

• 构造：O(n)
• 存储：O(n)

这就是它能处理很长字符串的根本原因。

---

13. 一个小例子：S = "ababa"

先不追求所有细节，只看结果直觉。

构造后，你可以从根开始：

• 读 'a'，得到子串 "a"
• 读 "ab"，得到 "ab"
• 读 "aba"，得到 "aba"
• 读 "bab"，也能走到某条路径
• 读 "ba"，也可以

总之，原串所有子串都会对应图上的某条路径。

而像 "aa" 这种不是子串的串，就走不出来。

这就是 SAM 最直观的用途：

它把“某串是否是子串”变成了“从根出发能否按字符一路走完”。

---

14. 最常见的 4 类应用

14.1 判断模式串是否为子串

把原串建 SAM。
然后拿模式串 T 从根开始走：

• 若某一步没有对应转移，T 不是子串
• 否则走完整个 T，说明它是子串

时间复杂度：

$$O(|T|)$$

---

14.2 不同子串个数

这是 SAM 的经典公式。

每个状态 v 贡献的新子串个数为：

$$len[v] - len[link[v]]$$

于是不同子串总数为：

$$\sum_{v \neq root} (len[v] - len[link[v]])$$

为什么对

前面说过，状态 v 对应的字符串长度区间是：

$$(len[link[v]] + 1) \sim len[v]$$

这个区间里的每种长度都对应一个不同子串。
区间长度就是：

$$len[v] - len[link[v]]$$

把所有状态加起来即可。

---

14.3 求每个子串出现次数

这也是很常见的。

先做一件事

每次新建一个 cur（不是 clone），令：

$$cnt[cur] = 1$$

表示这个状态对应的“新前缀”出现了一次。

然后按 len 从大到小拓扑统计

把每个状态的 cnt 累加到它的 link 上。

即：

$$cnt[link[v]] += cnt[v]$$

这样做完后：

• 一个状态 v 的 cnt[v]
• 就等于该状态所表示那一类字符串的出现次数

如果你要查某个模式串 T 的出现次数：

1. 先在 SAM 上走到对应状态 v
2. 答案就是 cnt[v]

---

14.4 最长公共子串（LCS）

给 S 建 SAM，再拿另一个串 T 在上面跑。

维护当前匹配长度 l 和当前状态 v：

• 若存在转移，直接走，l++
• 若不存在，就沿 link 跳，直到能走或回到根
• 过程中维护最大 l

最终得到 S 和 T 的最长公共子串长度。

这个算法复杂度是：

$$O(|S| + |T|)$$

比很多朴素方法高效得多。

---

15. SAM 与后缀数组、后缀树的关系

这几个经常被一起提。

后缀数组 SA

• 擅长排序后的后缀信息
• 做区间、排名、LCP 等很强
• 实现相对规整

后缀树

• 功能很强
• 理论漂亮
• 但实现偏重，常数大

后缀自动机 SAM

• 实现相对简洁
• 对“子串”问题很顺手
• 在线构造非常方便

竞赛里很多“子串统计/匹配”题，SAM 都是很好用的选择。

---

16. 初学者最容易混淆的点

误区 1：一个状态对应一个字符串

不对。
一个状态对应的是一类字符串。

---

误区 2：SAM 只管后缀

不对。
构造过程围绕后缀，但最终表示的是 所有子串。

---

误区 3：link[v] 就是删掉第一个字符后的那个字符串

不完全对。
它对应的是：

当前状态最长串的最长真后缀所在的状态

注意这里是“状态”，不是某个唯一字符串。

---

误区 4：clone 是“复制一个新串”

不是。
clone 是为了维护自动机最小化结构而引入的技术状态。

---

17. 如何真正理解 clone

可以记住这句话：

某个状态原本把多种长度、但 endpos 相同的字符串压在一起；加入新字符后，发现它们的后继行为不同了，于是要把这个等价类拆分。

而 clone 正是“拆分等价类”的实现方式。

所以 clone 的本质不是“新出现了一个子串”，而是：

原来分得太粗，现在必须细分。

---

18. 一份很实用的思维模型

你可以这样记 SAM：

根

表示空串。

一条路径

表示一个子串。

一个状态

表示若干个“结束位置完全相同”的子串。

len

这类子串里最长的长度。

link

往“更短但本质最接近的后缀类”跳。

clone

把一个状态拆成两份，避免“语义混住”。

这样会比死背定义更好记。

---

19. 常见扩展

除了上面几种，SAM 还常做这些：

• 所有子串按字典序第 k 小
• 多串最长公共子串
• 某些出现次数至少为 k 的最长子串
• 子串贡献统计
• 与 DP 结合做计数

很多题的套路其实都是：

1. 先建 SAM
2. 再在 DAG 上做 DP 或统计

---

20. 一句话总结

后缀自动机的本质是：

把一个串的所有子串，按 endpos 等价类压缩成线性大小的自动机。

它最重要的几个关键词是：

• 所有子串
• 最小 DFA
• endpos 等价类
• 后缀链接
• clone 拆分

如果你把这几个点想通，SAM 基本就算入门了。

---

下面这段是最值得背下来的“极简版”：

1. len[v]：状态 v 中最长串长度
2. link[v]：最长串的最长真后缀所在状态
3. 状态 v 代表长度区间 $$(len[link[v]]+1) \sim len[v]$$
4. 不同子串数 $$\sum (len[v]-len[link[v]])$$
5. 插入字符时，若遇到“已有转移但长度不对”，就 clone

如果你愿意，我可以下一条直接给你继续讲：

“用一个具体字符串手动画出 SAM 的构造全过程”，或者
“后缀自动机模板 + 经典题套路总结”。