后缀自动机（SAM）：字符串处理的“万能瑞士军刀”

如果说KMP是解决单一模式串匹配的“精准手术刀”，AC自动机是多模式串匹配的“战场扫描仪”，那么后缀自动机就是处理所有子串问题的“万能瑞士军刀”——它用极致的数学对称性，将任意字符串的所有子串信息压缩到了一个精巧的图结构中。

引言

在编程竞赛和工业级文本处理中，我们总会遇到这样的困境：给你一个长度高达10^6的字符串，你需要回答“某个子串出现了多少次？”“所有不同子串的总长度是多少？”“多个字符串的最长公共子串是什么？”单看每个问题都有特定解法，但能否用一个数据结构通吃所有？

传统的做法要么是建后缀数组（代码长、常数大），要么是建后缀树（空间开销大），而后缀自动机（Suffix Automaton, SAM） 提供了一种近乎完美的答案——它用O(n)的时间和空间，构造出一个包含原字符串所有子串信息的最小DFA（确定性有限状态自动机）。理解SAM，你就掌握了一把解决字符串问题的“万能钥匙”。

“如果说字符串是一幅藏宝图，那么SAM就是以最经济的方式，把图上所有路径（子串）都编码进了一个永不迷路的导航系统。”

前置知识

在开始之前，请确保你熟悉以下概念：

第一章：从问题出发——为什么需要后缀自动机

1.1 一切子串问题的核心

假设我们有一个字符串 s = "abcbc"。我们想知道：

• 子串 "bc" 出现了几次？（答案是2次）

• 总共有多少个本质不同的子串？（答案是13个）

• 是否存在一个子串 "cb" ？（答案是存在）

如果让你来设计一个数据结构解决所有这类问题，最朴素的想法是：把所有后缀插入到一棵Trie树中。这棵Trie树包含了所有子串（因为任何子串都是某个后缀的前缀），但它的大小是O(n²)级别。对于n=10^5，这棵树的内存会直接爆炸。我们需要一种压缩方式。

1.2 从“集合”到“等价类”的思维飞跃

SAM的核心思想是：不需要存储每个子串的具体位置，只需要存储它们在所有后缀中出现位置的“规律”。SAM利用一个叫 endpos 的概念（也叫right集合），把所有拥有相同出现位置集合的子串压缩成一个状态。

• 例如，在"abcbc"中，子串"bc"出现在位置2和4（结束下标），子串"c"也出现在位置3和5。

• 如果两个子串的endpos集合完全相同，那么它们在自动机中的“命运”就是一样的——它们可以被合并。

通过这种合并，SAM的状态数被压缩到了2n，转移边数压缩到了3n。这才是SAM既“万能”又“经济”的根本原因。

第二章：核心思想——理解endpos与link

2.1 什么是endpos等价类

定义：对于一个子串t，endpos(t) = t在s中所有结束位置的集合（位置从1开始计数）。

例如，s = "ababa"：

• endpos("a") = {1, 3, 5}

• endpos("ba") = {3, 5}

• endpos("aba") = {3, 5}

注意，"ba"和"aba"的endpos是相同的！它们属于同一个等价类。自动机会把它们压缩到同一个状态。

这引出了一个重要结论：同一个状态里的所有子串，互为后缀，且长度连续。也就是说，状态v代表了一系列长度在(len(link(v)), len(v)]之间的子串。

2.2 link指针——SAM的“失配”灵魂

如果说状态是SAM的“肉体”，那么 link指针就是SAM的“灵魂”。

link(v)指向的是状态v中最长子串的后缀中，属于另一个等价类的、长度最长的那个子串所在的状态。

如何理解link？
你可以把link理解为KMP的next数组在自动机上的泛化。在KMP中，匹配失败时，我们利用next回退到最长的相同前后缀。在SAM中，当我们从一个状态顺着字符找不到转移时，我们就顺着link指针跳转，直到找到一个有目标字符转移的状态或回到根节点。

• len[v]：状态v中最长子串的长度。

• len[link[v]]：状态v中最短子串的长度减1。

关键性质：顺着link指针从任意状态走到根节点，所经过的路径恰好覆盖了该状态中最长子串的所有不同后缀。

第三章：构造算法——在线增量构建

3.1 算法流程的直观理解

SAM的构造是一个在线算法，即逐个向字符串末尾添加字符，动态维护整个自动机。代码极其精炼，通常不超过30行。

我们定义：

• last：对应整个当前字符串的状态。

• size：状态总数。

• next：转移边（字典）。

• link：后缀链接。

• len：状态内最长子串长度。

核心代码模板及注释（C++）：

cpp

struct State {
int len, link; // len: 最长子串长度, link: 后缀链接
int next[26]; // 假设小写字母，实际可用map
};
State st[MAXN * 2]; // 2n空间
int sz, last;

void sam_init() {
st[0].len = 0;
st[0].link = -1;
sz = 1;
last = 0;
}

void sam_extend(char c) {
int cur = sz++; // 新建当前字符对应的状态
st[cur].len = st[last].len + 1;
int p = last;
// 步骤1: 从last开始，沿着link走，为没有'c'转移的状态添加指向cur的边
while (p != -1 && !st[p].next[c]) {
st[p].next[c] = cur;
p = st[p].link;
}
if (p == -1) { // 情况1: 走到了根节点之上，link指向根
st[cur].link = 0;
} else { // 情况2: p有'c'转移
int q = st[p].next[c];
if (st[p].len + 1 == st[q].len) { // 情况A: 直接连接
st[cur].link = q;
} else { // 情况B: 需要分裂节点
int clone = sz++; // 复制q
st[clone].len = st[p].len + 1;
memcpy(st[clone].next, st[q].next, sizeof(st[q].next)); // 复制转移
st[clone].link = st[q].link;
// 将p及其沿着link走的所有指向q的转移重定向到clone
while (p != -1 && st[p].next[c] == q) {
st[p].next[c] = clone;
p = st[p].link;
}
st[q].link = st[cur].link = clone; // 更新q和cur的link
}
}
last = cur; // 更新last
}

3.2 为什么需要“克隆”？

“克隆”是SAM构造中最烧脑的一步。简单来说，当我们添加新字符时，新状态cur需要一个正确的link。如果直接指向q不合法（因为q的长度太长了），我们就必须创建一个q的“副本”——clone。

clone拥有q的全部转移边，但其len更小（等于st[p].len + 1），并且它的link指向q原来的link。这样做保证了自动机的状态数依然是线性的，并且所有状态的len和link关系依然严格成立。

理解“克隆”的比喻：
想象一家公司（状态q）业务扩张得太快，新人（cur）无法直接归入q部门。于是，公司把q的核心业务抽离出来，成立一个更具普适性的“子公司”（clone），让q和cur都挂在clone下面。这样既保留了核心业务，又实现了灵活扩展。

第四章：经典例题精解——洛谷 P3804 【模板】后缀自动机 (SAM)

理论最终要服务于实战。我们以算法竞赛中最经典的模板题为例，展示SAM的完整落地。

4.1 题目呈现

题目来源：洛谷 P3804
题目描述：
给定一个只包含小写字母的字符串 SS（∣S∣≤106∣S∣≤106），请你求出 SS 的所有子串中，出现次数 ×× 该子串长度的最大值。

输入格式：一行，一个只含小写字母的字符串。
输出格式：一行，一个整数，表示答案。

4.2 解题思路推导（如何求出现次数）

4.3 完整AC代码（C++17）

cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;

struct State {
int len, link;
int next[26];
} st[MAXN << 1]; // 开两倍空间

int sz, last;
ll cnt[MAXN << 1]; // 记录每个状态的endpos大小

void sam_init() {
st[0].len = 0;
st[0].link = -1;
sz = 1;
last = 0;
memset(st[0].next, 0, sizeof(st[0].next));
}

void sam_extend(char ch) {
int c = ch – 'a';
int cur = sz++;
st[cur].len = st[last].len + 1;
cnt[cur] = 1; // 代表当前前缀的状态，出现次数初始为1
memset(st[cur].next, 0, sizeof(st[cur].next));

int p = last;
while (p != -1 && !st[p].next[c]) {
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 = sz++;
st[clone].len = st[p].len + 1;
memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
st[clone].link = st[q].link;
cnt[clone] = 0; // 克隆节点初始为0

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;
}

char s[MAXN];
int b[MAXN << 1], topo[MAXN << 1]; // 基数排序辅助数组

int main() {
scanf("%s", s);
int n = strlen(s);
sam_init();
for (int i = 0; i < n; i++) sam_extend(s[i]);

// 基数排序（计数排序）按len从小到大排序，等效于拓扑序
int max_len = n;
for (int i = 0; i < sz; i++) b[st[i].len]++;
for (int i = 1; i <= max_len; i++) b[i] += b[i-1];
for (int i = sz – 1; i >= 0; i–) topo[–b[st[i].len]] = i;

ll ans = 0;
// 逆序处理（len从大到小），累加endpos大小
for (int i = sz – 1; i > 0; i–) {
int v = topo[i];
cnt[st[v].link] += cnt[v];
if (cnt[v] > 1) ans = max(ans, cnt[v] * st[v].len);
}
printf("%lld\\n", ans);
return 0;
}

4.4 复杂度分析与解题心得

• 时间复杂度：构造 O(n×∣Σ∣)O(n×∣Σ∣)，其中 ∣Σ∣=26∣Σ∣=26（常数）；基数排序和DP统计 O(n)O(n)。整体完美通过 106106 的数据规模。

• 空间复杂度：状态数组 2n2n，转移数组 2n×262n×26，在 106106 下约占用 2×106×(4×27)≈216MB2×106×(4×27)≈216MB，需注意内存限制（通常512MB可通过）。

解题核心套路提炼：
做SAM的题，心里要时刻挂着 link树。绝大多数的计数问题，都是先建SAM，然后利用 link 指针作为父边构建出 link 树，在树上做树形DP（或拓扑累加）。只要算出了每个状态的 cnt（即 endpos 大小），你就拥有了子串出现次数的上帝视角。

总结

后缀自动机是字符串处理领域一颗璀璨的明珠。它的美妙之处在于，用近乎完美的数学结构（endpos等价类）实现了对庞大子串信息的最小无损压缩。虽然其构造算法（尤其是克隆操作）初次接触时略显晦涩，但一旦理解了核心思想，它将为你打开一扇高效处理字符串问题的大门。

三个关键点：

“后缀自动机教会我们：真正的智慧不在于记录所有细节，而在于发现细节背后的规律，并将其提炼为最优雅的‘等价’。”

参考文献与延伸阅读