引言
后缀自动机（Suffix Automaton，简称 SAM）是处理字符串问题的强大数据结构。它能够在 O(n) 时间内在线构建，将字符串的所有子串信息压缩到一个仅有 O(n) 个状态的有向无环图中。与后缀树和后缀数组相比，后缀自动机不仅空间更优，还能高效解决多种经典问题：统计不同子串数量、查找最长重复子串、计算第 k 小子串、多模式串匹配等。
本文将带你深入理解后缀自动机的核心原理，并用 Java 实现其增量构造算法，最后演示如何用它在线性时间内统计一个字符串中互不相同的子串总数。
核心概念
后缀自动机本质上是一个确定有限状态自动机（DFA），它识别字符串的所有后缀。为了将状态数控制在 O(n)，SAM 采用了巧妙的压缩策略：每个状态代表一组子串的结束位置集合（endpos 等价类）。
状态（State）
每个状态包含三个关键属性：
len：该状态所能表示的最长子串长度。若某状态由字符逐步扩展而来，len即为当前字符串前缀的长度。link（后缀链接）：指向当前状态的最长真后缀所对应的状态。它构成了一棵以初始状态为根的树，称为后缀链接树。next（转移函数）：一个从字符到状态的映射，表示在当前状态代表的子串后追加某字符，会转移到的目标状态。
endpos 等价类
对于字符串 s 的任意子串 t，定义 endpos(t) 为 t 在 s 中所有结束位置的集合。两个子串属于同一个 endpos 等价类，当且仅当它们的 endpos 集合完全相同。SAM 的每个状态恰好对应一个 endpos 等价类。
关键性质
- 状态数上界：对于长度为
n的字符串，SAM 最多有2n - 1个状态。 - 转移数上界：SAM 最多有
3n - 4个转移。 - 后缀链接树：
link指针构成一棵以初始状态（len = 0）为根的树。从任意状态沿link向上走到根，路径上的len值严格递减。
增量构建算法详解
后缀自动机的构建采用在线增量方式：逐个将字符添加到已构建的自动机末尾。设当前已处理前缀为 s，要加入字符 c 得到 s + c。
创建新状态
创建一个新状态 cur，其 len 值为 last.len + 1，其中 last 是表示整个当前字符串的状态。
添加转移
从 last 开始，沿后缀链接向上遍历。对于路径上的每个状态 p，如果 p 没有字符 c 的转移，则添加 p.next[c] = cur。这个过程相当于将新字符 c 对应的所有新后缀都挂到 cur 上。
处理已有转移的情况
如果在上述遍历中遇到某个状态 p 已经有字符 c 的转移（设转移到状态 q），则需要分两种情况处理：
情况一：p.len + 1 == q.len
此时 q 恰好就是 cur 的后缀链接目标，直接设置 cur.link = q 即可。
情况二：p.len + 1 < q.len
此时 q 代表了一组合法但过长的子串，不能直接将 cur 的后缀链接设为 q。需要克隆 q 得到一个副本 clone，将 clone.len 设为 p.len + 1，复制 q 的转移表和后缀链接，然后设置 q.link = cur.link = clone。最后，继续沿后缀链接向上，将所有原本指向 q 且通过字符 c 转移的状态，改为指向 clone。
克隆操作的核心目的是保持 endpos 等价类的正确划分。克隆状态拥有和原状态相同的转移能力，但 len 更短，因此它代表了更小的 endpos 等价类。
更新 last 指针
无论哪种情况，最后都将 last 更新为 cur，表示当前完整字符串对应的状态。
Java 完整实现
下面是后缀自动机的完整 Java 实现，包含状态定义、增量构建方法，以及一个实用的应用方法。
import java.util.*;
/**
* 后缀自动机（Suffix Automaton）Java 实现
* 支持在线 O(n) 构建，可用于统计不同子串数量、查找最长重复子串等问题。
*/
public class SuffixAutomaton {
/**
* SAM 状态节点
*/
static class State {
int len; // 该状态的最长子串长度
int link; // 后缀链接指向的状态编号
Map<Character, Integer> next; // 转移函数：字符 -> 目标状态编号
long dp; // 辅助字段，用于动态规划统计子串数量
State(int len) {
this.len = len;
this.link = -1;
this.next = new HashMap<>();
this.dp = -1;
}
}
private final List<State> states; // 所有状态的集合
private int last; // 当前完整字符串对应的状态编号
/**
* 构造一个空的后缀自动机，仅包含初始状态（根状态）
*/
public SuffixAutomaton() {
states = new ArrayList<>();
// 初始状态的 len 为 0，link 为 -1
states.add(new State(0));
last = 0;
}
/**
* 在线扩展：将字符 c 添加到自动机末尾
* 时间复杂度：均摊 O(1)
*/
public void extend(char c) {
// 1. 创建新状态 cur，其 len 为 last.len + 1
int cur = states.size();
states.add(new State(states.get(last).len + 1));
// 2. 从 last 开始沿后缀链接向上遍历，添加缺失的转移
int p = last;
while (p != -1 && !states.get(p).next.containsKey(c)) {
states.get(p).next.put(c, cur);
p = states.get(p).link;
}
// 3. 如果 p == -1，说明遍历到了根状态上方，cur 的后缀链接指向根
if (p == -1) {
states.get(cur).link = 0;
} else {
int q = states.get(p).next.get(c);
// 3a. 如果 p.len + 1 == q.len，直接设置后缀链接
if (states.get(p).len + 1 == states.get(q).len) {
states.get(cur).link = q;
} else {
// 3b. 需要克隆状态 q
int clone = states.size();
states.add(new State(states.get(p).len + 1));
// 复制 q 的转移表和后缀链接
states.get(clone).next.putAll(states.get(q).next);
states.get(clone).link = states.get(q).link;
// 将 q 和 cur 的后缀链接都指向 clone
states.get(q).link = clone;
states.get(cur).link = clone;
// 继续沿后缀链接向上，将所有指向 q 且通过 c 转移的改为指向 clone
while (p != -1 && states.get(p).next.get(c) == q) {
states.get(p).next.put(c, clone);
p = states.get(p).link;
}
}
}
// 4. 更新 last 指针
last = cur;
}
/**
* 从字符串构建完整的后缀自动机
*/
public void build(String s) {
for (char c : s.toCharArray()) {
extend(c);
}
}
/**
* 获取状态数量
*/
public int size() {
return states.size();
}
/**
* 获取指定编号的转移映射（调试用）
*/
public Map<Character, Integer> getTransitions(int stateId) {
return new HashMap<>(states.get(stateId).next);
}
/**
* 应用一：统计字符串中互不相同的子串数量
* 原理：每个状态 v（除根外）贡献 (len[v] - len[link[v]]) 个不同子串
* 时间复杂度：O(状态数)
*/
public long countDistinctSubstrings() {
long count = 0;
// 状态 0 是根状态，跳过
for (int i = 1; i < states.size(); i++) {
State st = states.get(i);
int linkLen = st.link == -1 ? 0 : states.get(st.link).len;
count += st.len - linkLen;
}
return count;
}
/**
* 应用二：按状态编号拓扑序（按 len 降序）排列，用于后续 DP
* 返回按 len 从大到小排序的状态编号数组
*/
public int[] getTopologicalOrder() {
int n = states.size();
int maxLen = 0;
for (State st : states) {
maxLen = Math.max(maxLen, st.len);
}
// 计数排序：按 len 分组
int[] cnt = new int[maxLen + 1];
for (State st : states) {
cnt[st.len]++;
}
for (int i = 1; i <= maxLen; i++) {
cnt[i] += cnt[i - 1];
}
int[] order = new int[n];
for (int i = n - 1; i >= 0; i--) {
order[--cnt[states.get(i).len]] = i;
}
// 反转得到降序
for (int i = 0; i < n / 2; i++) {
int tmp = order[i];
order[i] = order[n - 1 - i];
order[n - 1 - i] = tmp;
}
return order;
}
/**
* 应用三：查找最长重复子串的长度
* 若字符串中没有重复子串，返回 0
*/
public int longestRepeatedSubstring() {
int maxLen = 0;
// 有克隆状态时，非克隆状态的 link 所指向的状态对应的 len 即为重复子串长度
for (int i = 1; i < states.size(); i++) {
State st = states.get(i);
if (st.link != -1) {
maxLen = Math.max(maxLen, states.get(st.link).len);
}
}
return maxLen;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("SuffixAutomaton (").append(states.size()).append(" states):\n");
for (int i = 0; i < states.size(); i++) {
State st = states.get(i);
sb.append(" State ").append(i)
.append(": len=").append(st.len)
.append(", link=").append(st.link)
.append(", transitions=").append(st.next)
.append("\n");
}
return sb.toString();
}
// ==================== 主程序：测试与演示 ====================
public static void main(String[] args) {
// 测试字符串
String[] testCases = {
"abcbc",
"banana",
"aaaa",
"abcdefghijklmnopqrstuvwxyz"
};
for (String s : testCases) {
System.out.println("========================================");
System.out.println("输入字符串: \"" + s + "\"");
System.out.println("字符串长度: " + s.length());
SuffixAutomaton sam = new SuffixAutomaton();
sam.build(s);
System.out.println("SAM 状态数: " + sam.size());
System.out.println("不同子串数量: " + sam.countDistinctSubstrings());
System.out.println("最长重复子串长度: " + sam.longestRepeatedSubstring());
// 验证：暴力枚举所有子串并去重，对比 SAM 结果
Set<String> bruteForce = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
bruteForce.add(s.substring(i, j));
}
}
System.out.println("暴力枚举子串数量: " + bruteForce.size());
System.out.println("结果一致性: " + (sam.countDistinctSubstrings() == bruteForce.size() ? "✓" : "✗"));
}
// 演示 SAM 的完整结构
System.out.println("\n========================================");
System.out.println("SAM 结构演示 (字符串 \"ababa\"):");
SuffixAutomaton demo = new SuffixAutomaton();
demo.build("ababa");
System.out.println(demo);
}
}
代码解析
状态设计
State 类使用 HashMap<Character, Integer> 存储转移函数，以字符为键、目标状态编号为值。实际项目中，若字符集固定且较小（如仅小写字母），可将 HashMap 替换为固定大小的数组以获得更高性能。
extend 方法
这是后缀自动机的核心。每次调用 extend(c) 均摊时间复杂度为 O(1)，因为每个状态的 link 指针只会被遍历有限次。整个字符串构建过程的时间复杂度为 O(n)。
克隆处理
克隆（clone）是初学者最容易困惑的部分。它的本质是拆分一个 endpos 等价类：原状态 q 代表的子串集合中，长度大于 clone.len 的部分继续由 q 表示，长度不超过 clone.len 的部分改由 clone 表示。这样做保证了所有状态的转移逻辑仍然正确，同时维持了后缀链接树的性质。
不同子串计数
统计不同子串的公式非常优雅：对于每个非根状态 v，它贡献了 len[v] - len[link[v]] 个不同的子串。原因是状态 v 对应的所有子串长度范围为 (len[link[v]], len[v]]，这是一个左开右闭区间，恰好包含 len[v] - len[link[v]] 个整数长度，每种长度对应一个唯一子串。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 构建时间 | O(n) | 均摊，n 为字符串长度 |
| 状态数量 | ≤ 2n – 1 | 最坏情况为全不相同字符 |
| 转移数量 | ≤ 3n – 4 | 理论证明的上界 |
| 空间复杂度 | O(n) | 状态与转移的总存储 |
| 不同子串计数 | O(状态数) | 遍历所有状态一次 |
扩展应用
掌握后缀自动机后，你可以进一步探索以下问题：
- 第 k 小子串：在后缀链接树上进行动态规划，结合转移字典序遍历。
- 最长公共子串：对两个字符串分别构建 SAM，或在同一 SAM 上同时追踪两个字符串的状态。
- 出现次数统计：利用后缀链接树的子树求和，计算每个状态对应的 endpos 集合大小。
- 多模式串匹配：构建文本串的 SAM，然后在上面运行模式串的匹配过程。
总结
后缀自动机是字符串算法领域的一颗明珠。它以极其紧凑的 O(n) 空间存储了字符串所有子串的信息，构建过程简洁而优雅。本文实现的 Java 版本完整覆盖了核心算法，并提供了可直接运行的测试用例。理解后缀自动机的关键在于把握 endpos 等价类 的压缩思想，以及 克隆操作 如何巧妙地维护等价类的正确划分。掌握了这些，你就拥有了解决复杂字符串问题的利器。
