后缀数组与后缀自动机
第三十二章：后缀数组与后缀自动机 — 字符串的"终极索引"
给你一本 500 页的书，让你找出所有出现"算法"这个词的位置。你可以从头翻到尾（O(n)），也可以翻到书后面的索引页（O(log n)）。后缀数组就是字符串的"索引页"——它把字符串所有后缀排好序，让你能用二分查找在 O(m log n) 时间内找到任何长度为 m 的模式。
但如果你需要的不只是"找到模式在哪"，而是"这个字符串里有多少个不同的子串""最长的重复子串是什么"？这时就需要后缀自动机（SAM）——一个用 O(n) 空间编码所有子串信息的有限状态机。
这两个结构是字符串算法的"终极武器"。KMP 和 Rabin-Karp 解决的是"在文本中找一个模式"，而后缀数组和后缀自动机解决的是"关于这个字符串的所有子串，你想知道什么都行"。
Level 1 · 你需要知道的
1.1 后缀的概念
字符串 s = "banana" 的所有后缀：
| 编号 i | 后缀 s[i:] |
|---|---|
| 0 | banana |
| 1 | anana |
| 2 | nana |
| 3 | ana |
| 4 | na |
| 5 | a |
后缀数组（Suffix Array, SA） 就是把这些后缀按字典序排列后，记录它们的起始位置：
排序后：a(5), ana(3), anana(1), banana(0), na(4), nana(2)
所以 SA = [5, 3, 1, 0, 4, 2]。
为什么有用？ 任何子串都是某个后缀的前缀。如果后缀已排序，你可以用二分查找定位任何子串。
def build_suffix_array_naive(s: str) -> list[int]:
"""
朴素构建后缀数组：O(n² log n)
生成所有后缀，按字典序排序，返回起始位置
"""
n = len(s)
# 生成 (后缀, 起始位置) 对
suffixes = [(s[i:], i) for i in range(n)]
# 按字典序排序
suffixes.sort(key=lambda x: x[0])
# 返回排序后的起始位置
return [pos for _, pos in suffixes]
def search_pattern(text: str, pattern: str, sa: list[int]) -> list[int]:
"""
使用后缀数组 + 二分查找在文本中找模式
时间复杂度：O(m log n)，m = len(pattern), n = len(text)
"""
n = len(text)
m = len(pattern)
# 找左边界：第一个 >= pattern 的后缀
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
# 比较后缀的前 m 个字符与 pattern
suffix = text[sa[mid]:]
if suffix[:m] < pattern:
lo = mid + 1
else:
hi = mid
left = lo
# 找右边界：第一个 > pattern 的后缀
lo, hi = left, n
while lo < hi:
mid = (lo + hi) // 2
suffix = text[sa[mid]:]
if suffix[:m] <= pattern:
lo = mid + 1
else:
hi = mid
right = lo
return sorted(sa[left:right])
# 演示
text = "banana"
sa = build_suffix_array_naive(text)
print(f"后缀数组: {sa}") # [5, 3, 1, 0, 4, 2]
positions = search_pattern(text, "ana", sa)
print(f"'ana' 出现在位置: {positions}") # [1, 3]
1.2 LCP 数组 — 相邻后缀的公共前缀长度
LCP（Longest Common Prefix）数组：LCP[i] 表示排序后第 i 个后缀和第 i-1 个后缀的最长公共前缀长度。
对于 "banana" 的后缀数组 SA = [5, 3, 1, 0, 4, 2]：
| rank | SA[rank] | 后缀 | LCP |
|---|---|---|---|
| 0 | 5 | a | — |
| 1 | 3 | ana | 1 |
| 2 | 1 | anana | 3 |
| 3 | 0 | banana | 0 |
| 4 | 4 | na | 0 |
| 5 | 2 | nana | 2 |
LCP = [−, 1, 3, 0, 0, 2]
LCP 数组的威力：
- 最长重复子串 = max(LCP) = 3（"ana"）
- 不同子串个数 = n(n+1)/2 − sum(LCP) = 21 − 6 = 15
def build_lcp_array(text: str, sa: list[int]) -> list[int]:
"""
Kasai 算法：O(n) 构建 LCP 数组
核心思想：如果 suffix(sa[rank-1]) 和 suffix(sa[rank]) 的 LCP = k，
那么 suffix(sa[rank-1]+1) 和 suffix(sa[rank]+1) 的 LCP >= k-1
"""
n = len(text)
# rank[i] = 后缀 i 在后缀数组中的排名
rank = [0] * n
for i in range(n):
rank[sa[i]] = i
lcp = [0] * n
k = 0 # 当前 LCP 值
for i in range(n):
if rank[i] == 0:
k = 0
continue
# sa[rank[i] - 1] 是排序中前一个后缀的起始位置
j = sa[rank[i] - 1]
# 逐字符比较
while i + k < n and j + k < n and text[i + k] == text[j + k]:
k += 1
lcp[rank[i]] = k
# 关键：下一轮 LCP 至少是 k-1
if k > 0:
k -= 1
return lcp
# 演示
text = "banana"
sa = build_suffix_array_naive(text)
lcp = build_lcp_array(text, sa)
print(f"LCP 数组: {lcp}") # [0, 1, 3, 0, 0, 2]
# 最长重复子串
max_lcp = max(lcp)
max_idx = lcp.index(max_lcp)
print(f"最长重复子串: '{text[sa[max_idx]:sa[max_idx]+max_lcp]}'") # "ana"
# 不同子串个数
n = len(text)
total_substrings = n * (n + 1) // 2
distinct_substrings = total_substrings - sum(lcp)
print(f"不同子串个数: {distinct_substrings}") # 15
1.3 Kasai 算法的关键洞察
为什么 Kasai 算法是 O(n) 的？看起来里面有一个 while 循环在逐字符比较，不应该是 O(n²) 吗？
证明思路：变量 k 在整个循环中最多增加 n 次（因为 k ≤ n），而每次外层循环 k 最多减少 1。所以 k 的总增加量 ≤ n + n = 2n，即 while 循环总共执行不超过 2n 次。这是一个经典的摊还分析。
1.4 常见应用场景
| 问题 | 解法 |
|---|---|
| 字符串中是否包含模式 P | SA + 二分查找，O(m log n) |
| 最长重复子串 | max(LCP) |
| 不同子串个数 | n(n+1)/2 − sum(LCP) |
| 两个字符串的最长公共子串 | 拼接 s1 + '#' + s2，建 SA，找跨界 LCP |
| 第 k 小子串 | LCP 数组上做前缀和 |
1.5 常见错误
错误一：忘记在拼接字符串时加分隔符
# 错误：直接拼接
combined = s1 + s2 # "abc" + "bcd" = "abcbcd"
# 后缀 "cbcd" 会跨越两个字符串的边界，产生错误的 LCP
# 正确：使用不在字母表中的分隔符
combined = s1 + '\x00' + s2 # '\x00' 比任何字母都小
错误二：二分查找时比较整个后缀而非前缀
# 错误：比较整个后缀
if text[sa[mid]:] < pattern: # O(n) 每次比较
# 正确：只比较前 m 个字符
if text[sa[mid]:sa[mid]+m] < pattern: # O(m) 每次比较
Level 2 · 它是怎么运行的
2.1 倍增法构建后缀数组
朴素方法的瓶颈是排序时每次比较需要 O(n) 时间。倍增法的核心思想：先按第 1 个字符排序，再按前 2 个字符排序，再按前 4 个字符排序……每轮比较可以利用上一轮的结果在 O(1) 时间完成。
这是 Karp, Miller, Rosenberg (1972) 提出的思想，后来被 Manber 和 Myers (1993) 完善为后缀数组的标准构建算法。
def build_suffix_array_doubling(s: str) -> list[int]:
"""
倍增法构建后缀数组：O(n log² n)
思路：
- 第 0 轮：按每个后缀的第 1 个字符排序
- 第 k 轮：按每个后缀的前 2^k 个字符排序
- 第 k 轮的排序键 = (第 k-1 轮的 rank[i], 第 k-1 轮的 rank[i + 2^(k-1)])
因为第 k-1 轮已经正确排序了前 2^(k-1) 个字符，
所以第 k 轮只需要把两个"半段"的 rank 组合成一个二元组来排序。
"""
n = len(s)
# 初始化：按单个字符的 ASCII 值排序
sa = list(range(n))
rank = [ord(c) for c in s]
tmp = [0] * n
k = 1 # 当前比较的长度
while k < n:
# 排序键：(rank[i], rank[i+k])，i+k 越界时用 -1
def compare(a, b):
if rank[a] != rank[b]:
return rank[a] - rank[b]
ra = rank[a + k] if a + k < n else -1
rb = rank[b + k] if b + k < n else -1
return ra - rb
import functools
sa.sort(key=functools.cmp_to_key(compare))
# 重新计算 rank
tmp[sa[0]] = 0
for i in range(1, n):
# 如果和前一个相同，rank 相同；否则 rank + 1
if compare(sa[i], sa[i-1]) == 0:
tmp[sa[i]] = tmp[sa[i-1]]
else:
tmp[sa[i]] = tmp[sa[i-1]] + 1
rank = tmp[:]
# 如果所有 rank 都不同，排序已完成
if rank[sa[-1]] == n - 1:
break
k *= 2
return sa
时间复杂度分析：
- 外层循环 O(log n) 轮（k 每轮翻倍）
- 每轮排序 O(n log n)
- 总计 O(n log² n)
如果用基数排序替代比较排序，每轮变为 O(n)，总计 O(n log n)。
2.2 SA-IS 算法思路
SA-IS（Suffix Array — Induced Sorting）是 Nong, Zhang, Chan 在 2009 年提出的线性时间算法。它的核心思想非常精妙：
第一步：分类后缀为 S-type 和 L-type
- 如果 s[i:] < s[i+1:]（字典序），则 suffix(i) 是 S-type（Smaller）
- 如果 s[i:] > s[i+1:]（字典序），则 suffix(i) 是 L-type（Larger）
- 最后一个字符（通常是 '$'，最小字符）永远是 S-type
判断规则很简单：
- 如果 s[i] < s[i+1]，则 i 是 S-type
- 如果 s[i] > s[i+1]，则 i 是 L-type
- 如果 s[i] == s[i+1]，则 i 和 i+1 同类型
def classify_suffixes(s: str) -> list[bool]:
"""
分类每个后缀为 S-type (True) 或 L-type (False)
从右向左扫描一遍即可，O(n)
"""
n = len(s)
is_s_type = [False] * n
is_s_type[n - 1] = True # 最后一个永远是 S-type（'$' 最小）
for i in range(n - 2, -1, -1):
if s[i] < s[i + 1]:
is_s_type[i] = True
elif s[i] > s[i + 1]:
is_s_type[i] = False
else:
is_s_type[i] = is_s_type[i + 1]
return is_s_type
第二步：找 LMS（Left-Most S-type）后缀
LMS 后缀是"左边是 L-type，自己是 S-type"的后缀。LMS 后缀的数量不超过 n/2。
def find_lms_positions(is_s_type: list[bool]) -> list[int]:
"""找所有 LMS 位置"""
lms = []
for i in range(1, len(is_s_type)):
if is_s_type[i] and not is_s_type[i - 1]:
lms.append(i)
return lms
第三步：诱导排序（Induced Sorting）
这是 SA-IS 的核心——如果知道了 LMS 后缀的相对顺序，可以在 O(n) 时间内推导出所有后缀的顺序：
- 把 LMS 后缀放入 SA 的正确桶中（按首字符分桶）
- 从左到右扫描 SA，诱导 L-type 后缀的位置
- 从右到左扫描 SA，诱导 S-type 后缀的位置
第四步：递归
如果 LMS 后缀的顺序无法唯一确定（有相同的 LMS 子串），则递归处理。递归的问题规模不超过 n/2，所以总时间 T(n) = T(n/2) + O(n) = O(n)。
def sa_is_simplified(s: str) -> list[int]:
"""
SA-IS 算法简化实现（展示核心思想）
实际实现需要处理很多边界情况
"""
n = len(s)
if n <= 2:
# 基本情况
if n == 1:
return [0]
return [0, 1] if s[0] <= s[1] else [1, 0]
# Step 1: 分类
is_s_type = classify_suffixes(s)
# Step 2: 找 LMS
lms_positions = find_lms_positions(is_s_type)
# Step 3: 桶排序 + 诱导排序（此处省略完整实现）
# 实际中需要：
# 3a. 计算每个字符的桶边界
# 3b. 将 LMS 后缀放入桶尾
# 3c. 从左到右诱导 L-type
# 3d. 从右到左诱导 S-type
# Step 4: 如果 LMS 子串有重复，递归
# 4a. 给每个 LMS 子串编号
# 4b. 对编号序列递归调用 SA-IS
# 4c. 用递归结果确定 LMS 后缀的正确顺序
# 4d. 再次诱导排序得到最终 SA
# 这里退化为倍增法作为演示
return build_suffix_array_doubling(s)
2.3 后缀自动机（SAM）
后缀自动机是一个有向无环图（DAG），它接受且仅接受字符串 s 的所有后缀。更重要的是，它的每条从初始状态出发的路径都对应 s 的一个子串，且不同路径对应不同子串。
关键性质：
- 状态数 ≤ 2n-1
- 转移数 ≤ 3n-4
- 构建时间 O(n)
class SuffixAutomaton:
"""
后缀自动机（SAM）
每个状态代表一个"等价类"——endpos 集合相同的子串集合。
endpos(t) = 子串 t 在 s 中所有出现位置的结尾位置集合。
例如 s = "abcbc":
- endpos("bc") = {2, 4}
- endpos("c") = {2, 4}
- "bc" 和 "c" 属于同一个等价类（endpos 相同）
"""
class State:
def __init__(self):
self.len = 0 # 该状态对应的最长子串长度
self.link = -1 # 后缀链接（parent in suffix link tree）
self.trans = {} # 转移：字符 -> 状态编号
self.cnt = 0 # 该状态被多少个后缀经过（用于计数）
def __init__(self):
self.states = [self.State()] # states[0] = 初始状态
self.states[0].len = 0
self.states[0].link = -1
self.last = 0 # 上一个字符扩展后到达的状态
def extend(self, c: str):
"""
在线构建：添加一个字符 c
时间复杂度：摊还 O(1)
"""
cur = len(self.states)
self.states.append(self.State())
self.states[cur].len = self.states[self.last].len + 1
self.states[cur].cnt = 1
# 沿后缀链接向上走，添加转移
p = self.last
while p != -1 and c not in self.states[p].trans:
self.states[p].trans[c] = cur
p = self.states[p].link
if p == -1:
# 情况 1：一路走到根都没有 c 转移
self.states[cur].link = 0
else:
q = self.states[p].trans[c]
if self.states[p].len + 1 == self.states[q].len:
# 情况 2：不需要拆分
self.states[cur].link = q
else:
# 情况 3：需要克隆状态 q
clone = len(self.states)
self.states.append(self.State())
self.states[clone].len = self.states[p].len + 1
self.states[clone].link = self.states[q].link
self.states[clone].trans = self.states[q].trans.copy()
self.states[clone].cnt = 0
# 将 q 和 cur 都指向 clone
while p != -1 and self.states[p].trans.get(c) == q:
self.states[p].trans[c] = clone
p = self.states[p].link
self.states[q].link = clone
self.states[cur].link = clone
self.last = cur
def count_distinct_substrings(self) -> int:
"""
不同子串个数 = 所有状态的 (len - len(link)) 之和
因为每个状态代表 len - len(parent) 个不同子串
"""
total = 0
for i in range(1, len(self.states)):
parent_len = self.states[self.states[i].link].len
total += self.states[i].len - parent_len
return total
def longest_repeated_substring(self, s: str) -> str:
"""
最长重复子串：找 cnt >= 2 的状态中 len 最大的
需要先通过拓扑排序计算每个状态的 cnt
"""
n_states = len(self.states)
# 按 len 排序（桶排序）
max_len = max(st.len for st in self.states)
bucket = [0] * (max_len + 1)
for st in self.states:
bucket[st.len] += 1
for i in range(1, max_len + 1):
bucket[i] += bucket[i - 1]
order = [0] * n_states
for i in range(n_states):
bucket[self.states[i].len] -= 1
order[bucket[self.states[i].len]] = i
# 从长到短传播 cnt
for i in range(n_states - 1, -1, -1):
idx = order[i]
if self.states[idx].link >= 0:
self.states[self.states[idx].link].cnt += self.states[idx].cnt
# 找 cnt >= 2 的最长
best_len = 0
best_state = -1
for i in range(1, n_states):
if self.states[i].cnt >= 2 and self.states[i].len > best_len:
best_len = self.states[i].len
best_state = i
if best_state == -1:
return ""
# 从 best_state 回溯找子串（通过在 s 中搜索）
# 简化：直接在 s 中找长度为 best_len 的重复子串
for i in range(len(s) - best_len + 1):
sub = s[i:i + best_len]
if s.find(sub, i + 1) != -1:
return sub
return ""
# 演示
s = "abcbc"
sam = SuffixAutomaton()
for c in s:
sam.extend(c)
print(f"不同子串个数: {sam.count_distinct_substrings()}") # 12
print(f"最长重复子串: '{sam.longest_repeated_substring(s)}'") # "bc"
2.4 SAM 的状态含义 — endpos 等价类
SAM 中每个状态代表一个 endpos 等价类。endpos(t) 是子串 t 在 s 中所有出现位置的结尾位置集合。
例如 s = "aabbaab"：
- endpos("a") = {0, 1, 4, 5}
- endpos("aa") = {1, 5}
- endpos("aab") = {2, 6}
- endpos("ab") = {2, 6}
注意 "aab" 和 "ab" 的 endpos 相同！它们属于同一个等价类。
endpos 等价类的性质（Blumer et al., 1985）：
- 对于同一等价类中的子串 u 和 v（|u| ≤ |v|），u 是 v 的后缀
- 等价类形成一棵树（后缀链接树），父节点的 endpos 是子节点的超集
- 等价类最多 2n-1 个
这意味着 SAM 的后缀链接树其实就是"反向后缀树"！
2.5 后缀数组 vs 后缀树 vs 后缀自动机
| 特性 | 后缀数组 | 后缀树 | 后缀自动机 |
|---|---|---|---|
| 空间 | O(n) 整数 | O(n) 但常数大 | O(n) 状态+转移 |
| 构建时间 | O(n) SA-IS | O(n) Ukkonen | O(n) 在线 |
| 模式匹配 | O(m log n) | O(m) | O(m) |
| 编程复杂度 | 中等 | 高 | 中等 |
| 实际内存 | 5n~9n bytes | 20n~40n bytes | 10n~15n bytes |
| 适用场景 | 竞赛、工程 | 理论分析 | 子串计数类问题 |
实际建议：
- 竞赛中：后缀数组最常用（代码短、不容易写错）
- 子串计数/最长重复：SAM 更方便
- 工程中（如全文搜索）：后缀数组 + LCP（内存友好）
Level 3 · 规范怎么定义的
3.1 Karp, Miller, Rosenberg (1972)：倍增思想的起源
在论文 "Rapid Identification of Repeated Patterns in Strings, Trees and Arrays" 中，Karp, Miller, Rosenberg 提出了一个优美的思想：
要比较两个长度为 2k 的子串，只需比较它们的两个长度为 k 的"半段"。如果我们已经对所有长度为 k 的子串编了号（相同子串相同编号），那么长度为 2k 的子串可以用一个二元组 (编号_前半, 编号_后半) 来唯一标识。
这就是"倍增"（doubling）思想。它不仅用于后缀数组，还影响了：
- 最近公共祖先（LCA）的倍增算法
- 稀疏表（Sparse Table）
- 字符串哈希的快速比较
原始论文的精确表述：
定义 name_k(i) 为从位置 i 开始、长度为 2^k 的子串的"名字"（编号）。则：
- name_0(i) = s[i] 的字符编码
- name_{k+1}(i) = rank of (name_k(i), name_k(i + 2^k)) among all such pairs
最终后缀数组就是 name_⌈log n⌉ 的排列。
3.2 Manber & Myers (1993)：后缀数组的诞生
在论文 "Suffix Arrays: A New Method for On-Line String Searches" 中，Manber 和 Myers 正式定义了后缀数组，并给出了 O(n log n) 的构建算法和 O(m + log n) 的搜索算法。
他们的关键贡献：
-
定义了后缀数组和 LCP 数组的接口：明确了这两个数据结构可以替代后缀树解决大多数问题，且空间开销小得多。
-
搜索优化：朴素的二分查找是 O(m log n)，他们利用 LCP 信息将搜索加速到 O(m + log n)。
具体做法：维护搜索区间 [L, R] 与 pattern 的 LCP 长度 lcp_L 和 lcp_R。在比较中间元素 M 时，可以跳过 min(lcp_L, lcp_R) 个字符直接从不同的位置开始比较。
def search_manber_myers(text: str, pattern: str, sa: list[int],
lcp: list[int]) -> tuple[int, int]:
"""
Manber-Myers 加速搜索：O(m + log n)
思路：利用已知的 LCP 信息跳过字符比较
这里展示简化版本的思路
"""
n = len(text)
m = len(pattern)
# 计算 pattern 和 suffix(sa[i]) 的 LCP
def lcp_with_pattern(idx: int) -> tuple[int, int]:
"""返回 (lcp_length, comparison_result)"""
pos = sa[idx]
k = 0
while k < m and pos + k < n:
if pattern[k] < text[pos + k]:
return k, -1
elif pattern[k] > text[pos + k]:
return k, 1
k += 1
if k == m:
return k, 0 # pattern 是后缀的前缀
return k, -1 # 后缀比 pattern 短
# 标准二分找左边界（简化版，实际 Manber-Myers 用 LCP 加速）
lo, hi = 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
_, cmp = lcp_with_pattern(mid)
if cmp <= 0:
hi = mid - 1
else:
lo = mid + 1
left = lo
# 找右边界
lo, hi = left, n - 1
while lo <= hi:
mid = (lo + hi) // 2
lcp_len, cmp = lcp_with_pattern(mid)
if lcp_len == m: # 完全匹配
lo = mid + 1
elif cmp > 0:
lo = mid + 1
else:
hi = mid - 1
right = hi
return left, right
3.3 SA-IS (Nong, Zhang, Chan, 2009)：线性时间的突破
论文 "Two Efficient Algorithms for Linear Time Suffix Array Construction" 给出了迄今最简洁的线性时间后缀数组构建算法。
SA-IS 算法的形式化描述：
输入：字符串 S[0..n-1]，字母表大小 σ 输出：后缀数组 SA[0..n-1]
Algorithm SA-IS(S, n, σ):
1. 分类：从右到左扫描 S，将每个后缀分类为 S-type 或 L-type
2. 找 LMS：标记所有 LMS 位置（左邻是 L-type 的 S-type 位置）
3. 第一次诱导排序：
a. 将 LMS 后缀按出现顺序放入桶尾
b. 从左到右扫描 SA，诱导 L-type 后缀（放入桶头）
c. 从右到左扫描 SA，诱导 S-type 后缀（放入桶尾）
4. 给 LMS 子串命名：比较相邻 LMS 子串是否相同
5. 如果有重复名字：
a. 构造缩减问题 S₁（LMS 子串的名字序列）
b. 递归调用 SA-IS(S₁, n₁, σ₁)
c. 根据递归结果确定 LMS 后缀的正确顺序
6. 第二次诱导排序：用正确的 LMS 顺序重新执行步骤 3
7. 返回 SA
时间复杂度证明：
- 步骤 1-4, 6：都是 O(n)
- 步骤 5 的递归：问题规模 n₁ ≤ n/2（因为 LMS 位置之间至少间隔 2）
- 总时间：T(n) ≤ T(n/2) + cn = O(n)
SA-IS 为什么比 DC3/Skew 算法更快？
DC3（Kärkkäinen & Sanders, 2003）把后缀分成 mod 3 = 0 和 mod 3 ≠ 0 两组，递归规模是 2n/3。SA-IS 的递归规模是 n/2，且常数更小（不需要做 merge 步骤）。实测中 SA-IS 快 2-3 倍。
3.4 Blumer et al. (1985)：后缀自动机的理论基础
在 "The Smallest Automaton Recognizing the Subwords of a Text" 中，Blumer 等人证明了后缀自动机的若干关键定理：
定理 1（状态数上界）： 长度为 n 的字符串的 SAM，状态数不超过 2n-1（当 s = abbb...b 形式时取等）。
定理 2（转移数上界）： 转移数不超过 3n-4（当 s = abbb...bbc 形式时取等）。
定理 3（endpos 等价类性质）： 两个子串 u, v 属于同一等价类当且仅当 endpos(u) = endpos(v)。等价类之间形成一棵树（后缀链接树），叶子对应字符串的每个位置。
3.5 在线构建的正确性证明
SAM 的在线构建算法每次添加一个字符，关键是证明三种情况覆盖了所有可能：
设添加字符 c 之前的字符串为 s，当前状态为 last（对应整个字符串 s 的等价类）。
Case 1：从 last 沿后缀链接向上走，所有状态都没有 c 转移。
- 这意味着字符 c 从未在 s 中出现过。新状态 cur 的后缀链接指向根。
Case 2：走到状态 p，p 有 c 转移到 q，且 len(q) = len(p) + 1。
- 这意味着 q 代表的最长子串恰好是 p 代表的最长子串加上字符 c。新状态 cur 的后缀链接直接指向 q。
Case 3：走到状态 p，p 有 c 转移到 q，但 len(q) > len(p) + 1。
- 这意味着 q 代表的等价类需要被拆分。克隆 q 为 clone，clone.len = p.len + 1，然后重定向相关转移。
摊还 O(n) 的证明： 虽然每次 extend 可能沿后缀链接向上走多步，但每次 extend 最多增加 2 个状态和 3 条转移。后缀链接树的总深度是 O(n)，且每个转移只会被重定向一次。因此总时间 O(n)。
Level 4 · 边界与陷阱
4.1 竞赛中的后缀数组应用
例题 1：最长公共子串（两个字符串）
给定字符串 A 和 B，找它们的最长公共子串。
def longest_common_substring(a: str, b: str) -> str:
"""
方法：拼接 A + '#' + B，建后缀数组和 LCP 数组
答案 = LCP 数组中满足"相邻两后缀分属 A 和 B"的最大值
时间复杂度：O(n + m)（使用 SA-IS）
"""
separator = '#' # 确保不在 A 和 B 中出现
combined = a + separator + b
n = len(combined)
len_a = len(a)
sa = build_suffix_array_naive(combined) # 实际用 SA-IS
lcp = build_lcp_array(combined, sa)
best_len = 0
best_pos = 0
for i in range(1, n):
# 判断 sa[i] 和 sa[i-1] 是否分属两个字符串
in_a_curr = sa[i] < len_a
in_a_prev = sa[i - 1] < len_a
if in_a_curr != in_a_prev and lcp[i] > best_len:
best_len = lcp[i]
best_pos = sa[i]
return combined[best_pos:best_pos + best_len]
# 演示
print(longest_common_substring("ABABC", "BABCBA")) # "BABC"
例题 2：不同子串个数（SAM 解法）
def count_distinct_substrings_sam(s: str) -> int:
"""
用 SAM 在 O(n) 时间计算不同子串个数
每个状态贡献 len(state) - len(link(state)) 个子串
"""
sam = SuffixAutomaton()
for c in s:
sam.extend(c)
return sam.count_distinct_substrings()
# 验证：与后缀数组方法一致
s = "banana"
# SAM 方法
print(f"SAM: {count_distinct_substrings_sam(s)}")
# SA + LCP 方法
sa = build_suffix_array_naive(s)
lcp = build_lcp_array(s, sa)
n = len(s)
print(f"SA+LCP: {n * (n + 1) // 2 - sum(lcp)}")
例题 3：第 k 小子串
def kth_smallest_substring(s: str, k: int) -> str:
"""
找字典序第 k 小的不同子串
方法：SA + LCP，按 SA 顺序遍历后缀
SA[i] 对应的后缀贡献 len(s) - SA[i] - LCP[i] 个"新"子串
累加直到超过 k
"""
n = len(s)
sa = build_suffix_array_naive(s)
lcp = build_lcp_array(s, sa)
count = 0
for i in range(n):
# 后缀 sa[i] 贡献的新子串：
# 长度从 lcp[i]+1 到 n-sa[i]
new_substrings = n - sa[i] - lcp[i]
if count + new_substrings >= k:
# 第 k 个在这个后缀中
length = lcp[i] + (k - count)
return s[sa[i]:sa[i] + length]
count += new_substrings
return "" # k 超过子串总数
# 演示
s = "banana"
for k in range(1, 6):
print(f"第 {k} 小子串: '{kth_smallest_substring(s, k)}'")
4.2 工程中的实际应用
全文搜索引擎（如 Google Code Search）
Google 的 Code Search 使用了后缀数组作为底层索引。Russ Cox 在 2012 年的博客 "Regular Expression Matching with a Trigram Index" 中描述了这个系统：
- 对代码库建立后缀数组（或 trigram index 近似）
- 搜索时先用 SA 定位候选位置
- 再用正则引擎验证精确匹配
基因组比对（BWA, Bowtie）
现代基因组比对工具（如 BWA, Bowtie2）的核心是 FM-Index，它基于 BWT（Burrows-Wheeler Transform），而 BWT 本质上就是后缀数组的一个变换：
BWT[i] = S[SA[i] - 1]（后缀数组中每个后缀的前一个字符）
FM-Index 的优势：
- 压缩存储（人类基因组 3GB → FM-Index 约 1.5GB）
- 精确匹配 O(m)，不需要解压
数据压缩（bzip2）
bzip2 使用 BWT 作为压缩的关键步骤：
- 计算字符串的 BWT
- BWT 将相似的上下文聚集在一起
- 用 Move-to-Front + Huffman 压缩
4.3 面试中不直接考但相关的知识
面试中很少直接考后缀数组/SAM（太难实现了），但以下变体可能出现：
变体 1：最长重复子串（LeetCode #1044）
面试中通常期望 O(n log n) 的二分 + Rabin-Karp 解法，而非后缀数组。但知道后缀数组解法（O(n)）展示了更深的理解。
def longest_repeated_substring_binary_search(s: str) -> str:
"""
二分 + Rabin-Karp：O(n log n)
二分答案长度，用滚动哈希检查是否存在重复
"""
n = len(s)
MOD = (1 << 61) - 1
BASE = 131
def has_repeat(length: int) -> str:
"""检查是否存在长度为 length 的重复子串"""
if length == 0:
return ""
# 计算 base^length
power = pow(BASE, length, MOD)
# 滚动哈希
h = 0
for i in range(length):
h = (h * BASE + ord(s[i])) % MOD
seen = {h: [0]} # hash -> [起始位置列表]
for i in range(1, n - length + 1):
h = (h * BASE - ord(s[i - 1]) * power + ord(s[i + length - 1])) % MOD
h = (h + MOD) % MOD
if h in seen:
# 哈希冲突验证
for prev in seen[h]:
if s[prev:prev + length] == s[i:i + length]:
return s[i:i + length]
seen[h].append(i)
else:
seen[h] = [i]
return ""
# 二分答案长度
lo, hi = 0, n - 1
result = ""
while lo <= hi:
mid = (lo + hi) // 2
found = has_repeat(mid)
if found:
result = found
lo = mid + 1
else:
hi = mid - 1
return result
变体 2：重复的子字符串（LeetCode #459）
判断字符串 s 是否可以由某个子串重复多次构成。
def repeated_substring_pattern(s: str) -> bool:
"""
经典技巧：s + s 去掉首尾字符后，如果包含 s，则 s 有重复结构
为什么？如果 s = t * k（t 重复 k 次），则 s + s = t * 2k
去掉首尾字符后仍然包含长度为 n 的连续 t 序列
"""
doubled = (s + s)[1:-1]
return s in doubled
4.4 性能对比实验
import time
import random
import string
def benchmark_suffix_array_methods():
"""
对比不同后缀数组构建方法的实际性能
"""
sizes = [1000, 5000, 10000, 50000]
for n in sizes:
s = ''.join(random.choices(string.ascii_lowercase, k=n))
# 朴素方法 O(n² log n)
start = time.time()
sa_naive = build_suffix_array_naive(s)
t_naive = time.time() - start
# 倍增法 O(n log² n)
start = time.time()
sa_doubling = build_suffix_array_doubling(s)
t_doubling = time.time() - start
print(f"n={n:6d}: 朴素={t_naive:.4f}s, 倍增={t_doubling:.4f}s")
assert sa_naive == sa_doubling, "结果不一致！"
# benchmark_suffix_array_methods() # 取消注释运行
4.5 实现中的常见陷阱
陷阱 1：后缀自动机的内存管理
SAM 的状态数可达 2n-1，每个状态需要存储转移字典。对于大字母表（如 Unicode），内存可能爆炸。
# 问题：每个状态用 dict 存转移，26 个字母时开销大
class State:
trans: dict # Python dict 每个至少 64 bytes
# 优化：对于小字母表，用数组
class StateOptimized:
trans: list # [None] * 26，固定大小
陷阱 2：LCP 数组的 RMQ 预处理
很多后缀数组的应用需要快速查询"SA[i] 到 SA[j] 之间的 LCP 最小值"（Range Minimum Query）。如果每次 O(n) 扫描就失去了意义。
标准做法：对 LCP 数组预处理 Sparse Table，支持 O(1) RMQ。
import math
class SparseTable:
"""稀疏表：O(n log n) 预处理，O(1) 查询区间最小值"""
def __init__(self, arr: list[int]):
n = len(arr)
k = int(math.log2(n)) + 1 if n > 0 else 0
# table[j][i] = min(arr[i..i+2^j-1])
self.table = [[0] * n for _ in range(k)]
self.table[0] = arr[:]
for j in range(1, k):
for i in range(n - (1 << j) + 1):
self.table[j][i] = min(
self.table[j-1][i],
self.table[j-1][i + (1 << (j-1))]
)
# 预计算 log2
self.log = [0] * (n + 1)
for i in range(2, n + 1):
self.log[i] = self.log[i // 2] + 1
def query(self, l: int, r: int) -> int:
"""查询 arr[l..r] 的最小值，O(1)"""
if l > r:
l, r = r, l
j = self.log[r - l + 1]
return min(self.table[j][l], self.table[j][r - (1 << j) + 1])
def lcp_of_suffixes(text: str, sa: list[int], lcp: list[int],
i: int, j: int, sparse: SparseTable) -> int:
"""
查询后缀 i 和后缀 j 的 LCP
= min(LCP[rank[i]+1 .. rank[j]])（假设 rank[i] < rank[j]）
"""
n = len(text)
rank = [0] * n
for idx in range(n):
rank[sa[idx]] = idx
ri, rj = rank[i], rank[j]
if ri > rj:
ri, rj = rj, ri
# LCP 的性质：lcp(sa[a], sa[b]) = min(LCP[a+1..b])
return sparse.query(ri + 1, rj)
陷阱 3：后缀数组中的哨兵字符
许多算法要求在字符串末尾添加一个"哨兵字符"（通常是 '$' 或 '\x00'），它必须比字母表中所有字符都小。忘记添加会导致比较越界或结果错误。
def build_sa_with_sentinel(s: str) -> list[int]:
"""正确做法：添加哨兵"""
s = s + '\x00' # 添加哨兵，确保没有两个后缀完全相同
sa = build_suffix_array_naive(s)
# 去掉哨兵对应的位置（始终排在第一个）
return sa[1:] # sa[0] 始终是哨兵后缀
4.6 推荐学习路径
- 入门：先彻底理解朴素后缀数组 + Kasai LCP
- 进阶：实现倍增法（理解 KMR 思想）
- 竞赛选手：背 SA-IS 模板或使用 Python 的
sort()+ 倍增 - 研究/工程：理解 FM-Index、压缩后缀数组
4.7 本章总结
| 知识点 | 关键数字 |
|---|---|
| 后缀数组空间 | O(n) 个整数 |
| SA-IS 构建时间 | O(n) |
| 二分搜索时间 | O(m log n) → O(m + log n)（Manber-Myers） |
| LCP 数组构建 | O(n)（Kasai 算法） |
| SAM 状态数 | ≤ 2n-1 |
| SAM 转移数 | ≤ 3n-4 |
| 不同子串个数 | n(n+1)/2 − sum(LCP) |
后缀数组和后缀自动机代表了字符串算法的最高水平。它们把"关于子串的一切问题"都归结为"建一个结构，然后查询"。理解它们不仅能解题，更能帮你理解搜索引擎索引、基因组比对、数据压缩等工程系统的底层设计。