第10章 Searching Strings by Substring：按子串搜索字符串

把子串出现归约为后缀前缀查询，系统讲解后缀数组、LCP/Kasai、Skew 构造、后缀树互转和 McCreight suffix links。

学习目标

能解释“10 Searching Strings by Substring”如何用后缀数组、LCP 与后缀树把子串查询变成有序区间定位
能逐项核对Notation and Terminology、The Suffix Array、The Suffix Tree、Some Interesting Problems，不把平台页数或相邻章节主题冒充原版目录
能固定输入和参数，按“suffix-array query = O(m log n + occ)”手算一个最小样例，并找到输出或成本的首个分叉
能注入“遗漏唯一终止符或混淆 LCP 下标，使构造、比较与区间边界不一致”，保存基线、故障、恢复和同输入重放证据

来源、版次与独立重写边界

“10 Searching Strings by Substring”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“10 Searching Strings by Substring”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“用后缀数组、LCP 与后缀树把子串查询变成有序区间定位”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：10 Searching Strings by Substring

10.1 Notation and Terminology：在本页正文中以“用后缀数组、LCP 与后缀树把子串查询变成有序区间定位”的对象、状态、复杂度或工程边界核对。
10.2 The Suffix Array：在本页正文中以“用后缀数组、LCP 与后缀树把子串查询变成有序区间定位”的对象、状态、复杂度或工程边界核对。
10.3 The Suffix Tree：在本页正文中以“用后缀数组、LCP 与后缀树把子串查询变成有序区间定位”的对象、状态、复杂度或工程边界核对。
10.4 Some Interesting Problems：在本页正文中以“用后缀数组、LCP 与后缀树把子串查询变成有序区间定位”的对象、状态、复杂度或工程边界核对。

从“一次扫描为何不够”开始

searching strings by substring的朴素方案把 P 与每个文本起点逐字符比较，最坏 O(np)。当文本近似静态、查询很多时，应先支付索引构造成本，再把每次查询降到与 p、occ 有关。

在 T 末尾追加全局最小且原文本未出现的 $。令 suffix(i)=T[i..n]。关键等价是：

P=T[i..i+p-1] \quad\Longleftrightarrow\quad P\text{ prefixes }\mathrm{suffix}(i)

因此把 T 的全部 n 个后缀组成字典 SUF(T)，子串搜索就变成第9章的前缀搜索；匹配后缀与出现位置 i 一一对应。

先预测 banana$ 中 ana 的出现位置。后缀 anana$ 与 ana$ 都以 ana 开头，起点分别为1和3；排序后它们连续，因此一个后缀范围同时给出计数和位置列表。

终止符 $ 保证所有后缀 prefix-free：短后缀不会停在内部节点或与长后缀混同。若文本本身可能含 $，实现必须选域外 sentinel 或先重编码字母表。

后缀数组：只保存有序后缀的起点

suffix array不复制 n 条后缀。SA 含 n 个 0 到 n-1 的整数，占 O(n log n) 位；文本本身另占 O(n log sigma) 位。

\mathrm{suffix}(SA[0]) \lt \mathrm{suffix}(SA[1]) \lt \cdots \lt \mathrm{suffix}(SA[n-1])

对 P 做 lower-bound，再把“P 已耗尽”作为上界 comparator 做第二次搜索，得到所有以 P 开头的后缀区间。区间元素 SA[j] 就是出现位置。

普通二分做 O(log n) 次比较，每次最坏读 p 个字符：

T_{\mathrm{SA-search}} = O(p\log n+\mathrm{occ})

它的结构紧凑、连续，适合缓存和外存；但同一 P 前缀会在不同 mid 后缀上重复比较。

用 LCP 边界避免重扫模式

令 l、r 是 P 与当前左右边界后缀的 LCP；Llcp[M]、Rlcp[M] 分别保存二分树中左边界/右边界与中点后缀的 LCP。若 l 大于、等于或小于 Llcp[M]，可以直接推断 P 与中点的次序，或者从已知相等前缀之后继续比较。

每一步要么不读新字符并把范围减半，要么让 P 的已比较位置向右推进。故两次边界搜索合计：

T_{\mathrm{LCP-search}} = O(p+\log n+\mathrm{occ})

任意两个有序后缀 SA[i]、SA[j] 的 LCP 等于它们之间相邻 LCP 的最小值：

\mathrm{lcp}(i,j) = \min_{k=i}^{j-1}\mathrm{LCP}[k]

Llcp/Rlcp 可按二分区间自底向上在线性时间构造，也可在 LCP 数组上建 RMQ，按需常数时间取得该最小值。

最长公共前缀数组与 Kasai 线性构造

longest-common-prefix array有 n-1 项。逐对从头比较在 aaaa...$ 这类文本上会反复扫描，最坏 Theta(n^2)。

Kasai 先建 inverse SA：rank[i] 返回 suffix(i) 在 SA 中的位置。按文本起点 i 从左到右处理；若 suffix(i-1) 与其 SA 前驱共享 h 个字符，删除两者首字符后仍至少共享 max(h-1,0) 个字符。因此新比较可从 h-1 开始。

Kasai(T, SA):
  rank = inversePermutation(SA)
  h = 0
  for i in text order:
    q = rank[i]
    if q is not the first suffix:
      k = SA[q - 1]
      h = max(h - 1, 0)
      while T[i + h] == T[k + h]: h += 1
      LCP[q - 1] = h

h 每轮至多减1，总共至多减 n 次；它也不会越过文本末尾，因此总增加次数 O(n)。算法时间、额外空间都是 O(n)。

LCP 不是只为搜索服务。SA 区间的最小 LCP 给任意两后缀的公共前缀；高 LCP 区间对应重复片段；后缀树内部节点深度也正由这些数值决定。

后缀数组构造：从字符串比较变成原子项排序

最直观的 suffix-array construction（后缀数组构造）创建 n 个指针并用比较排序。虽然比较次数 O(n log n)，每次 suffix strcmp 最坏 Theta(n)，且指针重排导致正文随机访问，CPU 和 I/O 都很差。

Skew：2/3 采样、递归命名、常数比较归并

Skew/DC3 把位置分为 residue 1 与 residue 2/0 两组：

对 i mod 3 等于2或0的位置，取长度3的字符三元组，基数排序并按词典序命名；
若名字不唯一，对长度约 2n/3 的名字串递归建 SA，得到采样后缀 rank；
residue 1 后缀用 (T[i],rank[i+1]) 二元组基数排序；
归并两组时，按另一后缀 residue，用一或两个字符加采样 rank 常数时间比较。

不对称 2/3:1/3 划分正是归并简单的原因：跨组比较平移1或2个字符后，总能落入已排序采样组。递推式：

T(n) = T(2n/3)+O(n) = O(n)

每层只排序/扫描 O(n) 个整数二元组或三元组，所以 RAM 中使用 radix sort 为 O(n)；两级存储中把构造归约为 Sort(n) 次 I/O，能直接复用第5章外存原子项排序。

Skew(T):
  name triples at positions i mod 3 in {2, 0}
  recursively rank sampled suffixes when names repeat
  radix-sort residue-1 suffixes by (T[i], rank[i+1])
  merge sampled and residue-1 suffixes with constant-size keys

本页还介绍 scan-based 构造：每次把一块文本放入内存，构建块内后缀顺序，再与磁盘上的旧 SA 顺序归并。它的渐进 I/O 高于 Skew，却以顺序 pass、预取、压缩和很少 seek 换取慢磁盘上的稳定吞吐。这体现算法工程中“最优 I/O 总量”与“设备偏好顺序流”并非同一目标。

后缀树：全部后缀的压缩 Trie

suffix tree有 n 个叶，每个内部节点至少两个孩子，因此总节点 O(n)。长边标签不复制字符，只引用 T 的起点和长度；根到叶拼出的字符串恰是对应后缀。

模式 P 从根沿唯一可能的边向下，逐字符消费长边标签：

遇 mismatch，P 不出现；
P 在节点或边中间耗尽，得到 extended locus；
locus 下所有叶的起点就是 occ 个出现位置。

节点出边用完美哈希索引首字符，可最坏 O(1) 分支：

T_{\mathrm{ST-search}} = O(p+\mathrm{occ}), \qquad S_{\mathrm{ST}} = O(n)

若用排序边数组，分支为 O(log sigma)，总搜索 O(p log sigma+occ)。树的渐进空间为 O(n) 个对象，却有大量指针、分配和差局部性；不能仅凭同阶空间断言它比 SA 紧凑。

SA、LCP 与后缀树可以线性互转

从后缀树按词典边序 DFS，遇叶写其起点即可得到 SA；相邻叶最低公共祖先的字符串深度写入 LCP。每个节点和边访问一次，O(n)。

反向由 SA、LCP 构树时，按 SA 顺序逐叶插入，并维护节点深度递增栈。下一个 LCP 小于栈顶时弹栈；大于当前父深度时拆边建立该 LCP 深度的内部节点；再把新叶挂到当前父节点。

BuildSuffixTree(SA, LCP):
  stack = [root at depth 0]
  append leaf SA[0]
  for i from 1 to n-1:
    while stack.top.depth > LCP[i-1]: pop
    if stack.top.depth < LCP[i-1]:
      split previous edge at depth LCP[i-1]
      push new internal node
    append leaf SA[i] under stack.top

摊还证明很直接：每个内部节点只进栈、出栈一次，每个后缀只增加一个叶和至多一个内部节点。实践中常先用紧凑、顺序的 Skew/SA-IS 类算法建 SA，再用 Kasai 和栈生成树，而不是直接动态构树。

McCreight：用 suffix links 直接线性构树

McCreight algorithm按从长到短的 suffix(0)、suffix(1)... 插入。朴素增量构造每次从根扫描，在 aaaa...$ 上达到 Theta(n^2)。

suffix link满足：

s[z] = a\,s[\mathrm{SL}(z)]

内部节点 z 至少是两条后缀的 LCA；把这两后缀起点同时加1，它们的 LCP 正好删除首字符，所以对应 locus 存在，suffix link 定义良好。链接深度严格下降，最终到根，不会形成环。

插入 suffix(i) 时，已知前一后缀的 head 与 locus：

若前一 locus 已有 suffix link，直接跳到删除首字符后的 locus；
否则从其父的 suffix link 出发，只比较已知路径的分支首字符做 rescan，必要时拆边创建 link 目标；
从目标继续扫描 suffix(i) 尚未知的字符，找到新 head，拆边并挂入新叶。

新字符扫描指针整体只向右，总量 O(n)；rescan 的树深由 suffix-link 跳转控制，总边遍历也 O(n)。若动态出边用平衡搜索树，分支 O(log sigma)，得到：

T_{\mathrm{McCreight}} = O(n\log\sigma), \qquad S_{\mathrm{McCreight}} = O(n)

用期望常数哈希可降低实际分支成本。外存中树边跳转可能每步一次 I/O，所以直接 McCreight 不一定优于先建顺序 SA 再转树；平均 LCP 很短、树顶层可缓存时才可能有优势。

独立教学延伸：近似匹配、压缩与文本挖掘

k 个 substitution 的近似匹配

把 X=T#P 建成统一后缀索引。对每个文本起点，先用一次 LCP 跳过最长相同段，再越过一个 mismatch，重复至多 k+1 次。若 LCP 查询能借助 suffix tree LCA 或 LCP 数组 RMQ 在 O(1) 完成，总时间从 O(np) 降到 O(nk)。

任意两个后缀的 LCP 等于后缀树两叶 LCA 的字符串深度，也等于它们 SA rank 区间内 LCP 最小值。这连接了 LCA、RMQ 与 Cartesian tree，并使后缀索引成为很多看似无关问题的底层原语。

压缩与挖掘

重复子串对应 SA 中连续的高 LCP 区域，也对应后缀树的深内部节点。最长重复、最频繁固定前缀、文档间共享片段可在这些区间/子树上统计。

文本压缩器需要寻找当前位置之前的最长匹配，后缀树或动态后缀索引可返回匹配长度和来源位置；但在线窗口、动态更新与指针空间会改变工程选择。第13至15章会进一步把排序、压缩与索引结合。

用三个独立预言机验收

对小文本，用朴素扫描产生每个模式的出现位置；SA 搜索区间、后缀树 locus 和扫描结果排序后必须一致。构造层另做不变式检查：SA 是 0..n-1 的排列且后缀递增；LCP 每项等于相邻后缀朴素 LCP；树每叶恰好一个后缀，长边拼接正确。

覆盖空模式、单字符、全重复、全不同、周期文本、嵌入零字节、Unicode 编码边界和 sentinel 冲突。随机文本测平均，aaaa... 与 ababab... 测最坏重复扫描。

性能记录构造 CPU、峰值内存、顺序/随机 I/O、SA/LCP 字节、树节点/边/指针字节、查询字符比较、RMQ 次数、输出 occ 和缓存命中。只报告查询 O(p+occ) 会隐藏构造成本和后缀树常数。

先预测，再操作三个章专属实验

分步1 / 3

1. 成本模型与工作集

在“10 Searching Strings by Substring”中先预测层级和访问模式如何改变“suffix-array query = O(m log n + occ)”，再切换工作集与局部性；最终结果相同不代表代价相同。

Cost-model laboratory

10 Searching Strings by Substring

用后缀数组、LCP 与后缀树把子串查询变成有序区间定位

工作集所在层级

规模8192

传输256

相对成本8×

suffix-array query = O(m log n + occ)

不变量：所有后缀恰出现一次并保持词典序，查询区间与朴素匹配结果一致

可重放工程合同

“10 Searching Strings by Substring”的实验必须保留：文本 hash、SA、LCP、比较区间、匹配位置、构造阶段与朴素预言机。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

练习

问题 1：正式目录。 “10 Searching Strings by Substring”的公开目录边界是什么，平台如何证明没有把其他章主题混入？

问题 2：最小反例。 怎样验证“suffix-array query = O(m log n + occ)”不是只写在页面上的公式？

问题 3：恢复证据。 怎样证明“遗漏唯一终止符或混淆 LCP 下标，使构造、比较与区间边界不一致”已经修复？

本章回顾

P 在 i 出现当且仅当 P 是 suffix(i) 的前缀，子串搜索归约为后缀前缀搜索。
后缀数组只存 n 个起点，匹配后缀形成连续区间。
普通 SA 查询 O(p log n+occ)，LCP 边界复用把它降为 O(p+log n+occ)。
LCP 数组保存相邻后缀公共前缀，区间最小值回答任意两后缀 LCP。
Kasai 以 h-1 下界复用前一后缀比较，线性构造 LCP。
Skew 用 2/3 采样与三元组命名，把 SA 构造归约为原子项排序。
后缀树是所有后缀的压缩 Trie，以 O(n) 结构支持 O(p+occ) 查询。
SA、LCP 与后缀树可通过 DFS 或深度栈在线性时间互转。
McCreight suffix links 删除前缀首字符并复用 locus，避免二次扫描。
LCP/RMQ/LCA 还支持 k-mismatch、重复发现、压缩和文本挖掘。