字符串算法

第 1 章 学习目标与导论

1.1 本章在算法知识体系中的位置

字符串算法（string algorithm，研究字符串（字符序列）上模式匹配、索引、压缩、比对等操作的算法集合，“string” 源自拉丁语 “stringere” 意为”拉紧、束缚”，中世纪英语引申为”由字符组成的序列”）是算法知识体系中”文本处理”专题的核心模块。它位于算法体系的”高级专题层”，向上承接 algorithm/数组与动态数组 与 algorithm/树，向下衔接 algorithm/动态规划（字符串 DP）、algorithm/线段树（后缀数组上 RMQ）、algorithm/图算法（AC 自动机的状态图）等具体应用。

学习本章前，读者应当已经掌握：

• algorithm/算法分析基础与学习路线：渐近复杂度、主定理、平摊分析
• algorithm/数组与动态数组：字符串的数组表示、随机访问
• algorithm/树：Trie 树、二叉树遍历
• cs-fundamentals/离散数学：等价关系、自动机理论、BFS

掌握本章后，读者将为后续学习 algorithm/KMP字符串匹配、algorithm/动态规划（编辑距离、回文）、algorithm/网络流（后缀自动机合并）等高级主题奠定坚实基础。

1.2 学习目标

本章遵循 Bloom 分类法，按认知层级递进组织学习目标：

1. 记忆（Remember）：复述字符串匹配的形式化定义，识别朴素匹配 $O(nm)$、KMP $O(n+m)$、Boyer-Moore 最坏 $O(n/m)$ 子线性平均、AC 自动机 $O(n+M)$ 等复杂度结论。
2. 理解（Understand）：解释字符串匹配算法从 1960s 朴素匹配到 KMP/Boyer-Moore 1977、Rabin-Karp 1987、Aho-Corasick 1975、Manber-Myers 1990 后缀数组、Ukkonen 1995 后缀树、DC3 2003 线性后缀排序的演进脉络。
3. 应用（Apply）：使用 KMP 前缀函数、Z 函数、Rabin-Karp 滚动哈希、Boyer-Moore 坏字符与好后缀、Sunday 算法编写可运行的 Python/C++/Java 代码。
4. 分析（Analyze）：对比 AC 自动机与 KMP、后缀数组与后缀树、后缀自动机与后缀树的代数约束与复杂度差异，论证 fail 指针构建的 BFS 正确性。
5. 评估（Evaluate）：评估后缀数组倍增 $O(n \log n)$、DC3/SA-IS 线性 $O(n)$ 算法在工程实践中的权衡，分析 height 数组与 LCP 的关系，推导后缀自动机 endpos 等价类性质。
6. 创造（Create）：设计面向开源项目（grep、ripgrep、Linux grep -F、HTTP 路由、DNA 序列比对、IDE 自动补全、LZ77/LZW 压缩）的字符串算法解决方案。

1.3 阅读建议

• 零基础读者：先通读第 2 章了解历史背景，跟随第 5-7 章学习朴素匹配、KMP、Rabin-Karp，最后回看第 3-4 章形式化定义与理论推导。
• 有算法基础读者：重点关注第 8-9 章 Boyer-Moore 与 Z 函数、第 10 章 AC 自动机、第 11-12 章后缀数组与后缀自动机。
• 进阶读者：直接研读第 13 章字符串 DP、第 16 章工程实践、第 17 章案例研究、第 18 章习题。

第 2 章 历史动机与演进

2.1 1960s：文本编辑器与编译器的早期需求

字符串匹配的系统性研究始于 1960s。早期文本编辑器（如 TECO、QED）与编译器（如 SNOBOL4）需要高效的字符串查找功能。最初采用朴素匹配（Brute-Force），即主串每个位置尝试与模式串对齐比较：

• TECO（Text Editor and Corrector，1962，MIT PDP-1）：第一个支持正则表达式风格搜索的编辑器，使用朴素匹配。
• SNOBOL4（1967，贝尔实验室）：由 Farber、Griswold、Polonsky 开发的字符串处理语言，其模式匹配需求直接推动了字符串算法的研究。
• QED（1969，Berkeley）：Ken Thompson 在 QED 中实现了第一个正则表达式引擎，采用 NFA 模拟。

朴素匹配的最坏复杂度为 $O(nm)$（$n$ 为主串长度，$m$ 为模式串长度），在处理长文本时性能不足。这促使研究者寻找线性或子线性算法。

2.2 1975：Aho-Corasick 多模式匹配

1975 年，Alfred V. Aho（贝尔实验室，师从 John Hopcroft）与 Margaret J. Corasick 在 Communications of the ACM 第 18 卷第 6 期发表论文《Efficient string matching: An aid to bibliographic search》。该论文解决了书目检索中”在长文本中同时查找多个关键词”的需求：

• 核心贡献：将 KMP 的前缀函数思想推广到 Trie 树，引入 fail 指针（failure link，指当前节点对应字符串的最长真后缀在 Trie 中的对应节点），构建 AC 自动机。
• 复杂度：预处理 $O(M)$（$M$ 为所有模式串总长），匹配 $O(n + z)$（$z$ 为匹配总数）。
• 应用：成为 Unix fgrep（即 grep -F）的核心算法，至今仍是多模式匹配的工业标准。

Aho-Corasick 自动机被广泛用于入侵检测系统（Snort、Suricata）、DNA 序列扫描、垃圾邮件过滤等场景。

2.3 1977：KMP 与 Boyer-Moore 同年发表

1977 年是字符串匹配算法的”奇迹年”，两篇里程碑论文同年发表：

2.3.1 Knuth-Morris-Pratt（KMP）算法

Donald E. Knuth（Stanford）、James H. Morris（CMU，时在 SNOBOL4 项目中遇到类似问题）、Vaughan R. Pratt（Stanford）合作在 SIAM Journal on Computing 第 6 卷第 2 期发表论文《Fast pattern matching in strings》。

• 核心思想：预处理模式串构造 前缀函数 $\pi[i]$（pattern[0..i] 的最长相等真前后缀长度），失配时主串指针不回退，模式串指针跳到 $\pi[j-1]$。
• 复杂度：$O(n+m)$，是第一个保证最坏情况线性的字符串匹配算法。
• 历史趣闻：Morris 在 1969 年为 SNOBOL4 实现字符串搜索时独立发现了该算法，Knuth 与 Pratt 在 1970 年也独立发现，三人 1977 年联合发表。

2.3.2 Boyer-Moore 算法

Robert S. Boyer 与 J. Strother Moore（均任职于 SRI International）在 Communications of the ACM 第 20 卷第 10 期发表论文《A fast string searching algorithm》。

• 核心思想：从右向左扫描模式串，结合 坏字符规则（bad character rule）与 好后缀规则（good suffix rule）跳过不可能匹配的位置。
• 复杂度：预处理 $O(m + |\Sigma|)$，平均 $O(n/m)$（子线性！），最坏 $O(nm)$（朴素 BM）或 $O(n+m)$（带 Galil 规则或 Apostolico-Giancarlo 变体）。
• 实际性能：在英文文本中通常比 KMP 快 3-5 倍，是 GNU grep、Ag（Silver Searcher）等工具的默认算法。

2.4 1987：Rabin-Karp 随机化算法

1987 年，Richard M. Karp（UC Berkeley，1985 年图灵奖得主）与 Michael O. Rabin（Hebrew University，1976 年图灵奖得主）在 IBM Journal of Research and Development 第 31 卷第 2 期发表论文《Efficient randomized pattern-matching algorithms》。

• 核心思想：将模式串与主串子串映射为多项式哈希值，利用 滚动哈希（rolling hash）在 $O(1)$ 时间内从窗口 $[i, i+m)$ 推出 $[i+1, i+1+m)$ 的哈希值。
• 复杂度：平均 $O(n+m)$，最坏 $O(nm)$（哈希冲突），但冲突概率可通过大质数或双模数降至可忽略。
• 应用：多模式匹配、二维模式匹配（图像）、 plagiarism 检测、rsync 增量同步算法的核心。

2.5 1990：Manber-Myers 后缀数组

1990 年，Udi Manber（Arizona 大学，后任 Google 工程副总裁）与 Gene Myers（Arizona 大学，后任 Celera Genomics 副总裁，参与人类基因组计划）在 SIAM Journal on Computing 第 22 卷第 5 期发表论文《Suffix arrays: A new method for on-line string searches》。

• 动机：后缀树（Weiner 1973、McCreight 1976）虽功能强大，但实现复杂、空间开销大（$O(n|\Sigma|)$）。Manber-Myers 提出后缀数组作为”空间高效的后缀树替代”。
• 核心结构：将字符串所有后缀按字典序排序，存储起始下标。
• 构建算法：倍增法 $O(n \log n)$，配合 Rank 数组实现 $O(\log n)$ 时间的 LCP 查询。
• 应用：人类基因组计划的核心数据结构、Burrows-Wheeler Transform（BWT）与 bzip2 压缩、生物信息学序列比对。

2.6 1995：Ukkonen 在线后缀树构造

1995 年，Esko Ukkonen（Helsinki 大学）在 Algorithmica 第 14 卷第 3 期发表论文《On-line construction of suffix trees》。

• 背景：Weiner 1973 与 McCreight 1976 的后缀树构造算法均为离线（需已知完整字符串）。Ukkonen 提出了第一个 在线（on-line）算法：字符逐个加入，每加入一个字符后缀树立即可用。
• 核心技巧：隐式后缀树（implicit suffix tree）+ 活动点（active point，由 active_node、active_edge、active_length 三元组描述）+ 后缀链接（suffix link）。
• 复杂度：$O(n)$ 时间与空间（固定字符集）或 $O(n \log |\Sigma|)$（可变字符集）。
• 应用：生物信息学（最长重复子串、最长公共子串）、数据压缩（LZ77 窗口优化）、字符串索引。

2.7 2003：DC3 线性后缀排序

2003 年，Juha Kärkkäinen（Helsinki 大学）与 Peter Sanders（Karlsruhe 工业大学）在 Journal of the ACM 第 53 卷第 6 期发表论文《Simple linear work suffix array construction》（DC3 算法，又称 skew algorithm）。

• 动机：Manber-Myers 倍增法 $O(n \log n)$ 在基因组规模（$10^9$）下仍较慢，需线性算法。
• 核心思想：将后缀按下标 $\bmod 3$ 分为两组：$S_{12}$（下标 mod 3 ≠ 0）与 $S_0$（下标 mod 3 = 0）。先递归排序 $S_{12}$，再利用 $S_{12}$ 的排序结果线性排序 $S_0$，最后归并。
• 复杂度：$O(n)$ 时间与空间，递归深度 $T(n) = T(2n/3) + O(n) = O(n)$（主定理）。
• 应用：成为后续 SA-IS（Nong-Zhang-Chan 2009）算法的基础。

2.8 2009：SA-IS 线性归纳排序

2009 年，Ge Nong、Sen Zhang、Wai Hong Chan 在 Data Compression Conference 发表论文《Linear suffix array construction by almost pure induced-sorting》。

• 改进：相比 DC3，SA-IS 纯基于归纳排序（induced sorting），无递归，常数更小。
• 核心概念：将后缀分为 S-type 与 L-type，识别 LMS（leftmost S-type）字符，先排序 LMS 后缀，再诱导排序其他后缀。
• 复杂度：$O(n)$ 时间与空间，是目前最快的线性后缀排序算法之一。

2.9 后缀自动机的演进

后缀自动机（suffix automaton，又称 DAWG，Directed Acyclic Word Graph）由 Blumer、Blumer、Ehrenfeucht、Haussler、McConnell 于 1985 年在论文《Complete inverted files for efficient text retrieval and analysis》中正式构造。其核心性质：

• 状态数上界 $2n - 1$，转移数上界 $3n - 4$（由 Blumer 等人证明）。
• 状态对应字符串子串的 endpos 等价类（endpos equivalent class，结束位置集合相同的子串归为一类）。
• 在线构造 $O(n)$（固定字符集）或 $O(n \log |\Sigma|)$（map 实现）。

后缀自动机因其简洁性与线性复杂度，成为竞赛与工程中处理子串问题的利器。

2.10 算法演进时间线总览

timeline
    title 字符串算法演进时间线
    1962 : TECO 朴素匹配
    1967 : SNOBOL4 模式匹配需求
    1969 : Thompson QED 正则引擎
    1973 : Weiner 后缀树 (离线 O(n))
    1975 : Aho-Corasick 多模式自动机
    1976 : McCreight 后缀树改进
    1977 : KMP (SIAM J.) 与 Boyer-Moore (CACM) 同年发表
    1985 : Blumer 等人后缀自动机 (DAWG)
    1987 : Rabin-Karp 滚动哈希
    1990 : Manber-Myers 后缀数组
    1995 : Ukkonen 在线后缀树
    2003 : Karkkainen-Sanders DC3 线性后缀排序
    2009 : Nong-Zhang-Chan SA-IS 归纳排序

第 3 章 形式化定义

3.1 字符串的基本概念

定义 3.1（字符串）：字符串 $S$ 是字符集 $\Sigma$ 上的有限序列，记作 $S = S[0]S[1]\cdots S[n-1]$，其中 $S[i] \in \Sigma$，$n = |S|$ 为字符串长度。空串记作 $\varepsilon$，$|\varepsilon| = 0$。

定义 3.2（子串与子序列）：

• 子串（substring）：$S[i..j] = S[i]S[i+1]\cdots S[j]$，要求 $0 \le i \le j < |S|$。子串是连续的。
• 子序列（subsequence）：从 $S$ 中删除零个或多个字符（不改变剩余字符顺序）得到的序列，不必连续。
• 前缀（prefix）：$S[0..i]$，即从位置 0 开始的子串，$0 \le i < |S|$。真前缀（proper prefix）要求 $i < |S| - 1$。
• 后缀（suffix）：$S[i..|S|-1]$，即到末尾的子串。真后缀（proper suffix）要求 $i > 0$。

定义 3.3（字符串匹配）：给定主串 $T = T[0..n-1]$ 与模式串 $P = P[0..m-1]$（$m \le n$），字符串匹配问题是寻找所有 位移（shift）$s \in [0, n-m]$ 使得：

即对任意 $0 \le j < m$，$T[s+j] = P[j]$。匹配集合记作：

定义 3.4（边界）：字符串 $S$ 的边界（border）是 $S$ 的最长真前缀同时也是 $S$ 的后缀。即 $\text{Border}(S) = S[0..b-1]$ 满足 $S[0..b-1] = S[|S|-b..|S|-1]$，且 $b < |S|$ 最大。

3.2 前缀函数的形式化定义

定义 3.5（前缀函数）：模式串 $P$ 的前缀函数 $\pi: \{0,1,\ldots,m-1\} \to \mathbb{N}$ 定义为：

即 $\pi[i]$ 是 $P[0..i]$ 的最长边界的长度。约定 $\pi[0] = 0$。

性质 3.1（前缀函数的递推性）：对任意 $i \ge 1$，

3.3 Z 函数的形式化定义

定义 3.6（Z 函数）：字符串 $S$ 的 Z 函数 $Z: \{0,1,\ldots,n-1\} \to \mathbb{N}$ 定义为：

即 $Z[i]$ 是从位置 $i$ 开始与 $S$ 的前缀的最长公共前缀长度。约定 $Z[0] = 0$（或 $|S|$，依实现而定）。

Z-box：维护区间 $[l, r]$ 使得 $r$ 最大且 $S[l..r]$ 是 $S$ 的前缀，用于 $O(1)$ 转移。

3.4 后缀数组的形式化定义

定义 3.7（后缀数组）：给定字符串 $S$（长度 $n$），其第 $i$ 个后缀为 $\text{suffix}(i) = S[i..n-1]$。后缀数组 $\text{SA}[0..n-1]$ 是 $[0, n-1]$ 的排列，使得后缀按字典序升序排列：

定义 3.8（Rank 数组）：Rank 是 SA 的反函数：$\text{Rank}[\text{SA}[i]] = i$，即后缀 $\text{suffix}(j)$ 在排序中的名次为 $\text{Rank}[j]$。

定义 3.9（Height 数组）：相邻后缀的 LCP（最长公共前缀）：

约定 $\text{height}[0] = 0$。

性质 3.2（LCP 与 RMQ 的转化）：对任意 $i < j$，

此性质将任意两后缀的 LCP 查询转化为 RMQ（Range Minimum Query）问题。

3.5 后缀自动机的形式化定义

定义 3.10（后缀自动机）：字符串 $S$ 的后缀自动机 $\text{SAM}(S) = (Q, q_0, F, \delta)$ 是识别 $S$ 所有后缀的最小 DFA：

• $Q$：状态集，每个状态对应一个 endpos 等价类。
• $q_0$：初始状态。
• $F$：接受状态集（含 $S$ 完整后缀的状态）。
• $\delta: Q \times \Sigma \to Q$：转移函数。

定义 3.11（endpos 集合）：子串 $w$ 的 endpos 集合为 $w$ 在 $S$ 中所有出现位置的结束下标集合：

定义 3.12（endpos 等价类）：两个子串 $u, v$ 等价（记 $u \equiv v$）当且仅当 $\text{endpos}(u) = \text{endpos}(v)$。等价类构成 $Q$ 的元素。

性质 3.3（endpos 等价类的嵌套）：若 $u \equiv v$ 且 $|u| \le |v|$，则 $u$ 是 $v$ 的后缀。等价类按 endpos 集合的包含关系构成树形结构（parent 树）。

定理 3.1（SAM 状态数上界）：$|S| = n$ 的 SAM 状态数 $|Q| \le 2n - 1$，转移数 $|\delta| \le 3n - 4$。

3.6 AC 自动机的形式化定义

定义 3.13（AC 自动机）：模式串集合 $P = \{P_1, P_2, \ldots, P_k\}$ 的 AC 自动机 $\text{AC}(P) = (Q, q_0, F, \delta, \text{fail})$：

• $Q$：Trie 节点集，每节点代表一个前缀。
• $q_0$：Trie 根。
• $F$：终止状态集（模式串结尾节点）。
• $\delta: Q \times \Sigma \to Q$：goto 函数，Trie 的转移。
• $\text{fail}: Q \to Q$：fail 函数，$\text{fail}(v)$ 指向 $v$ 路径所代表字符串的最长真后缀在 Trie 中对应的节点。

性质 3.4（fail 链的正确性）：对任意节点 $v$，沿着 fail 链 $v \to \text{fail}(v) \to \text{fail}(\text{fail}(v)) \to \cdots \to q_0$，所经过节点代表的字符串恰好是 $v$ 路径所代表字符串的所有真后缀（按长度递减）。

3.7 字符串匹配决策树

flowchart TD
    Start[字符串匹配问题] --> Q1{模式串数量?}
    Q1 -->|单模式| Q2{字符集大小?}
    Q1 -->|多模式| Q3{是否需流式处理?}

    Q2 -->|小字符集, 在线| KMP[KMP O n+m]
    Q2 -->|大字符集, 英文文本| BM[Boyer-Moore 平均 O n/m]
    Q2 -->|需多模式扩展| RK[Rabin-Karp 滚动哈希]
    Q2 -->|需 Z 函数分析| Z[Z 函数 O n+m]

    Q3 -->|是, 流式| AC[Aho-Corasick O n+M]
    Q3 -->|否, 全量加载| Q4{需后缀查询?}

    Q4 -->|仅需前缀查询| TRIE[Trie 树]
    Q4 -->|需任意子串| Q5{主串可变?}

    Q5 -->|主串固定, 多查询| SA[后缀数组 O n log n + 查询]
    Q5 -->|主串可变, 在线| SAM[后缀自动机 O n]

    KMP --> END[返回匹配位置]
    BM --> END
    RK --> END
    Z --> END
    AC --> END
    TRIE --> END
    SA --> END
    SAM --> END

第 4 章 理论推导

4.1 KMP 失配函数的正确性证明

定理 4.1（KMP 正确性）：给定主串 $T$ 与模式串 $P$，KMP 算法在 $O(n+m)$ 时间内找到 $P$ 在 $T$ 中的所有出现位置。

证明：

（1）失配时不漏匹配：假设已匹配 $P[0..j-1]$ 与 $T[i-j..i-1]$，在 $T[i]$ 与 $P[j]$ 失配。下一个可能的匹配位置 $s$ 必须满足 $s > i - j$ 且 $P[0..j-1]$ 的后缀 $P[s-(i-j)..j-1]$ 等于 $P$ 的前缀。即：

这正是 $P[0..j-1]$ 的边界定义。最长的边界长度为 $\pi[j-1]$，故 $s_{\min} = i - \pi[j-1]$。跳到 $j = \pi[j-1]$ 后，已匹配前缀 $P[0..\pi[j-1]-1]$ 与 $T[i-\pi[j-1]..i-1]$ 自动对齐，无需回退主串指针。

（2）复杂度分析：匹配阶段，主串指针 $i$ 从 0 单调增至 $n-1$，共 $n$ 次增加。模式串指针 $j$ 每次成功匹配增加 1，每次失配减少 $j - \pi[j-1] \ge 1$。$j$ 的总增加次数 $\le n$（受 $i$ 限制），故 $j$ 的总减少次数 $\le n$。总操作数 $O(n)$。预处理类似分析得 $O(m)$。$\square$

4.2 Z 函数算法推导

Z 函数核心思想：维护 Z-box $[l, r]$，其中 $S[l..r]$ 是 $S$ 的前缀且 $r$ 最大。计算 $Z[i]$ 时：

• 若 $i > r$：无法利用已有信息，暴力扩展。
• 若 $i \le r$：$S[i..r] = S[i-l..r-l]$，故 $Z[i] \ge \min(Z[i-l], r-i+1)$，从该长度继续扩展。

算法：

def z_function(s):
    """Z 函数：Z[i] 为 s[i..] 与 s[0..] 的最长公共前缀长度"""
    n = len(s)
    z = [0] * n
    l, r = 0, 0  # Z-box [l, r]
    for i in range(1, n):
        if i <= r:
            # 利用 Z-box 内的对称性
            z[i] = min(z[i - l], r - i + 1)
        # 暴力扩展
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        # 更新 Z-box
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    z[0] = n  # 约定 Z[0] = n
    return z

复杂度证明：内层 while 循环每次成功扩展使 $r$ 严格增加，$r$ 从 0 单调增至 $n-1$，故总扩展次数 $O(n)$。外层循环 $n$ 次。总计 $O(n)$。

4.3 AC 自动机 fail 指针构建的正确性

定理 4.2（fail 指针 BFS 正确性）：按 BFS 顺序计算 fail 指针，对节点 $v$（其父节点为 $u$，转移字符为 $c$），$\text{fail}(v) = \delta(\text{fail}(u), c)$（$\delta$ 为 goto 函数，递归沿 fail 链查找）。

证明：

归纳基础：根节点 $q_0$ 的 fail 为自身；根的子节点 fail 均为 $q_0$（其路径字符串长度 1，无真后缀在 Trie 中）。

归纳步骤：假设 $u$ 的 fail 已正确计算。$v$ 路径代表字符串 $S = S_u + c$。$S$ 的最长真后缀 $S'$ 必为 $S_u$ 的某个真后缀 + $c$，而 $S_u$ 的所有真后缀在 Trie 中的对应节点恰为沿 $\text{fail}(u)$ 链的所有节点。故 $S'$ 在 Trie 中对应节点 = 沿 $\text{fail}(u)$ 链找到的第一个有字符 $c$ 转移的节点的 $c$ 子节点。$\square$

复杂度：BFS $O(M)$，每个节点 fail 计算沿链回溯的总次数受 fail 深度递减性约束，均摊 $O(1)$。

4.4 后缀数组倍增算法推导

倍增算法核心思想：第 $k$ 轮按后缀的前 $2^k$ 个字符排序。利用第 $k-1$ 轮的 Rank，第 $k$ 轮的排序关键字为 $(\text{rank}_k[i], \text{rank}_k[i + 2^{k-1}])$，可用基数排序 $O(n)$ 完成。共 $\log n$ 轮，总计 $O(n \log n)$。

算法骨架：

def build_sa_doubling(s):
    """后缀数组倍增法：O(n log^2 n) 简化版（Python 内置排序）"""
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
    k = 1
    while k < n:
        # 关键字：(rank[i], rank[i+k] or -1)
        sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]]
            prev_key = (rank[sa[i - 1]], rank[sa[i - 1] + k] if sa[i - 1] + k < n else -1)
            curr_key = (rank[sa[i]], rank[sa[i] + k] if sa[i] + k < n else -1)
            if curr_key != prev_key:
                tmp[sa[i]] += 1
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:
            break
        k *= 2
    return sa

复杂度证明：每轮排序 $O(n \log n)$（Python 排序）或 $O(n)$（基数排序），共 $O(\log n)$ 轮，总计 $O(n \log^2 n)$ 或 $O(n \log n)$。

4.5 DC3 线性算法推导

DC3（skew algorithm）核心思想：将后缀按下标 $\bmod 3$ 分组：

• $S_{12} = \{ \text{suffix}(i) \mid i \bmod 3 \ne 0 \}$：下标 $\equiv 1, 2 \pmod 3$ 的后缀。
• $S_0 = \{ \text{suffix}(i) \mid i \bmod 3 = 0 \}$：下标 $\equiv 0 \pmod 3$ 的后缀。

步骤：

1. 递归排序 $S_{12}$：将每个 $S_{12}$ 中的后缀 $\text{suffix}(i)$ 用三元组 $(S[i], S[i+1], S[i+2])$ 编码（不足补 0），递归排序。递归规模 $\frac{2n}{3}$，递归式 $T(n) = T(2n/3) + O(n) = O(n)$（主定理）。
2. 排序 $S_0$：$\text{suffix}(i)$ ($i \equiv 0 \pmod 3$) 可表示为 $(S[i], \text{suffix}(i+1))$，而 $\text{suffix}(i+1) \in S_{12}$ 已排序，故 $S_0$ 可在 $O(n)$ 内排序。
3. 归并：比较 $\text{suffix}(i) \in S_{12}$ 与 $\text{suffix}(j) \in S_0$ 时，分情况用 $S_{12}$ 的排序结果。

复杂度：$T(n) = T(2n/3) + O(n) = O(n)$。

4.6 SA-IS 线性算法概述

SA-IS（Suffix Array Induced Sorting）核心思想：

1. 字符分类：将每个位置 $i$ 标记为 S-type（$S[i] < S[i+1]$ 或 $S[i] = S[i+1]$ 且 $i+1$ 为 S-type）或 L-type（否则）。
2. LMS 字符：L-type 后紧跟 S-type 的位置称为 LMS（Leftmost S-type）。
3. 诱导排序：
   • 先对 LMS 后缀命名排序。
   • 递归处理 LMS 子串。
   • 利用 LMS 排序结果诱导排序 L-type 与 S-type 后缀。

复杂度：递归规模 $\le n/2$，$T(n) = T(n/2) + O(n) = O(n)$。

4.7 后缀自动机 endpos 性质证明

定理 4.3（endpos 等价类的结构）：对字符串 $S$，每个 endpos 等价类 $C$ 中的子串按长度排序构成连续区间 $[\text{minlen}(C), \text{maxlen}(C)]$，其中 $\text{maxlen}(C)$ 为 $C$ 中最长子串长度，$\text{minlen}(C) = \text{maxlen}(\text{link}(C)) + 1$（$\text{link}$ 为后缀链接）。

证明：

设 $C$ 中最长子串为 $w$（$|w| = \text{maxlen}(C)$）。对 $C$ 中任意子串 $u$，由 $\text{endpos}(u) = \text{endpos}(w)$ 知 $u$ 是 $w$ 的后缀（性质 3.3）。$w$ 的所有后缀按长度降序排列，endpos 集合按包含关系递增。存在临界点：长度 $\ge \text{minlen}(C)$ 的后缀 endpos 集合相同（属于 $C$），长度 $< \text{minlen}(C)$ 的后缀 endpos 集合严格增大（属于父类）。$\square$

推论 4.1（SAM 状态数上界 $2n-1$）：每次添加字符至多新增 2 个状态，初始 1 个状态，故 $|Q| \le 2n - 1$。

推论 4.2（转移数上界 $3n-4$）：通过 SAM 与生成树的对应关系可证转移数 $\le 3n - 4$（$n \ge 3$）。

4.8 Boyer-Moore 好后缀规则推导

坏字符规则：失配于 $T[i] \ne P[j]$ 时，查找 $T[i]$ 在 $P[0..j-1]$ 中最右出现位置 $k$，移动 $j - k$（若 $T[i]$ 不在 $P$ 中，移动 $j + 1$）。

好后缀规则：已匹配 $P[j+1..m-1]$（好后缀 $u$），查找 $u$ 在 $P[0..j]$ 中最右出现位置 $k$（要求 $P[k-1] \ne P[j]$，避免再次失配），移动 $j - k + 1$。若无此 $k$，查找 $u$ 的最长前缀同时也是 $P$ 的后缀，移动相应距离。

取最大：实际移动距离取坏字符与好后缀规则的较大值，保证不漏匹配。

子线性平均复杂度：在字符集较大、模式串较短时，每次跳跃常达 $m$，平均 $O(n/m)$。最坏情况（如 $T = P = \text{"AAA...A"}$）退化为 $O(nm)$，需 Galil 规则改进至 $O(n+m)$。

第 5 章 朴素匹配与 Sunday 算法

5.1 朴素匹配算法

算法描述：主串每个位置 $i$ 尝试与模式串对齐，逐字符比较，失配则 $i$ 右移一位。

def brute_force_search(text, pattern):
    """朴素字符串匹配：返回所有匹配起始位置"""
    n, m = len(text), len(pattern)
    result = []
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            result.append(i)
    return result

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(brute_force_search(text, pattern))  # [10]

C++ 实现：

#include <vector>
#include <string>
using namespace std;

// 朴素字符串匹配：返回所有匹配起始位置
vector<int> bruteForceSearch(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    vector<int> result;
    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) ++j;
        if (j == m) result.push_back(i);
    }
    return result;
}

Java 实现：

import java.util.ArrayList;
import java.util.List;

public class BruteForceSearch {
    /** 朴素字符串匹配：返回所有匹配起始位置 */
    public static List<Integer> bruteForceSearch(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) j++;
            if (j == m) result.add(i);
        }
        return result;
    }
}

复杂度：

• 最好情况 $O(n)$：每个位置立即失配（如 $T = \text{"ABCDEFG"}, P = \text{"XYZ"}$）。
• 最坏情况 $O(nm)$：每次比较至最后一位失配（如 $T = \text{"AAAA...A"}, P = \text{"AAA...AB"}$）。

5.2 Sunday 算法

算法描述：Boyer-Moore 的简化变体，由 Daniel M. Sunday 1990 年提出。失配时考察主串中模式串后一位字符 $T[i + m]$：

• 若 $T[i + m]$ 不在模式串中，模式串直接跳到 $T[i + m + 1]$ 之后，移动 $m + 1$。
• 若 $T[i + m]$ 在模式串中最右出现位置为 $k$，移动 $m - k$。

def sunday_search(text, pattern):
    """Sunday 字符串匹配算法"""
    n, m = len(text), len(pattern)
    if m == 0:
        return [0]
    # 预处理：每个字符在模式串中最右出现位置
    last_pos = {}
    for i, ch in enumerate(pattern):
        last_pos[ch] = i
    result = []
    i = 0
    while i <= n - m:
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            result.append(i)
        # 移动距离由 T[i+m] 决定
        if i + m >= n:
            break
        next_ch = text[i + m]
        if next_ch in last_pos:
            i += m - last_pos[next_ch]
        else:
            i += m + 1
    return result

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(sunday_search(text, pattern))  # [10]

复杂度：

• 最好情况 $O(n/m)$：每次跳跃 $m+1$。
• 最坏情况 $O(nm)$：退化情形。
• 实践中常优于 Boyer-Moore，因实现简单且常数小。

5.3 Horspool 算法

Boyer-Moore 的另一简化变体，由 R. Nigel Horspool 1980 年提出。仅使用坏字符规则，且坏字符取自当前匹配窗口的最后一个字符：

def horspool_search(text, pattern):
    """Horspool 字符串匹配算法（Boyer-Moore 简化变体）"""
    n, m = len(text), len(pattern)
    if m == 0:
        return [0]
    # 预处理：每个字符对应的移动距离
    shift = {}
    for i in range(m - 1):
        shift[pattern[i]] = m - 1 - i
    result = []
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and text[i + j] == pattern[j]:
            j -= 1
        if j < 0:
            result.append(i)
        # 移动距离由窗口最后一个字符决定
        last_ch = text[i + m - 1] if i + m - 1 < n else ''
        i += shift.get(last_ch, m)
    return result

# 示例
print(horspool_search("GEEKS FOR GEEKS", "GEEK"))  # [0, 10]

第 6 章 KMP 算法详解

6.1 KMP 算法核心思想

KMP 算法（Knuth-Morris-Pratt，由 Donald Knuth、James Morris、Vaughan Pratt 于 1977 年在 SIAM Journal on Computing 第 6 卷第 2 期发表论文《Fast pattern matching in strings》系统化，三人独立发现后联合发表）通过预处理模式串构造 前缀函数 $\pi$，失配时利用 $\pi$ 跳过已匹配前缀，主串指针不回退。

6.2 前缀函数构建

def build_prefix_function(pattern):
    """构建 KMP 前缀函数 pi
    pi[i] = pattern[0..i] 的最长真前后缀长度
    """
    m = len(pattern)
    pi = [0] * m
    j = 0  # 当前最长相等前后缀长度
    for i in range(1, m):
        # 失配则沿 pi 链回退
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        # 匹配则扩展
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

# 示例
pattern = "ABABCABAB"
pi = build_prefix_function(pattern)
print(f"模式串: {pattern}")
print(f"pi 数组: {pi}")  # [0, 0, 1, 2, 0, 1, 2, 3, 4]

手动模拟：模式串 $P = \text{"ABABCABAB"}$

6.3 KMP 状态机

KMP 可视为 DFA（确定有限自动机），状态 $j$ 表示已匹配 $j$ 个字符，转移函数 $\delta(j, c)$：

stateDiagram-v2
    [*] --> S0
    S0 --> S1: A
    S0 --> S0: B/C/其他
    S1 --> S2: B
    S1 --> S1: A
    S1 --> S0: C/其他
    S2 --> S3: A
    S2 --> S0: B
    S2 --> S1: A
    S3 --> S4: B
    S3 --> S2: A
    S3 --> S0: C/其他
    S4 --> S5: C
    S4 --> S3: B
    S4 --> S0: A
    S5 --> S6: A
    S5 --> S0: B
    S5 --> S4: C
    S6 --> S7: B
    S6 --> S1: A
    S6 --> S0: C
    S7 --> S8: A
    S7 --> S0: B
    S7 --> S2: C
    S8 --> S4: B (匹配, 跳转 pi[8]=4)
    S8 --> S3: A
    S8 --> S0: C
    S8 --> [*]: 匹配成功

6.4 KMP 完整实现

Python 实现：

def kmp_search(text, pattern):
    """KMP 字符串匹配：返回所有匹配起始位置
    时间复杂度 O(n+m)，空间复杂度 O(m)
    """
    n, m = len(text), len(pattern)
    if m == 0:
        return [0]

    # 预处理：构建前缀函数
    pi = build_prefix_function(pattern)

    # 匹配阶段
    result = []
    j = 0  # 模式串指针
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            result.append(i - m + 1)
            j = pi[j - 1]  # 继续查找重叠匹配

    return result

def build_prefix_function(pattern):
    m = len(pattern)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp_search(text, pattern))  # [10]

# 重叠匹配示例
text2 = "AAAAA"
pattern2 = "AA"
print(kmp_search(text2, pattern2))  # [0, 1, 2, 3]

C++ 实现：

#include <vector>
#include <string>
using namespace std;

// 构建前缀函数
vector<int> buildPrefixFunction(const string& pattern) {
    int m = pattern.size();
    vector<int> pi(m, 0);
    int j = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        pi[i] = j;
    }
    return pi;
}

// KMP 匹配
vector<int> kmpSearch(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (m == 0) return {0};
    vector<int> pi = buildPrefixFunction(pattern);
    vector<int> result;
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            result.push_back(i - m + 1);
            j = pi[j - 1];
        }
    }
    return result;
}

Java 实现：

import java.util.ArrayList;
import java.util.List;

public class KMPSearch {
    /** 构建前缀函数 */
    public static int[] buildPrefixFunction(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];
        int j = 0;
        for (int i = 1; i < m; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        return pi;
    }

    /** KMP 字符串匹配 */
    public static List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (m == 0) {
            result.add(0);
            return result;
        }
        int[] pi = buildPrefixFunction(pattern);
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                result.add(i - m + 1);
                j = pi[j - 1];
            }
        }
        return result;
    }
}

6.5 KMP 的应用

6.5.1 最小循环节

定理 6.1：字符串 $S$（长度 $n$）的最小循环节长度为 $n - \pi[n-1]$，当且仅当 $n \bmod (n - \pi[n-1]) = 0$ 时 $S$ 是循环串。

def min_period(s):
    """求字符串 s 的最小循环节长度"""
    n = len(s)
    pi = build_prefix_function(s)
    period = n - pi[n - 1]
    if n % period == 0:
        return period
    return n  # 无循环节，整个字符串为循环节

# 示例
print(min_period("abcabcabc"))  # 3
print(min_period("abcab"))      # 5（无循环节）
print(min_period("aaaa"))       # 1

6.5.2 最长回文前缀

def longest_palindrome_prefix(s):
    """利用 KMP 求字符串最长回文前缀"""
    # 构造 s + '#' + reverse(s)，求前缀函数
    rev = s[::-1]
    combined = s + '#' + rev
    pi = build_prefix_function(combined)
    return pi[-1]

# 示例
print(longest_palindrome_prefix("abacaba"))  # 7（整个串是回文）
print(longest_palindrome_prefix("abcba"))    # 5
print(longest_palindrome_prefix("abcb"))     # 1（仅 'a'）

第 7 章 Rabin-Karp 算法

7.1 滚动哈希原理

多项式哈希：字符串 $S = S[0]S[1]\cdots S[m-1]$ 的哈希值为：

其中 $b$ 为基数（通常 256 或 131），$p$ 为大质数（如 $10^9 + 7$）。

滚动更新：从窗口 $[i, i+m)$ 到 $[i+1, i+1+m)$：

7.2 Rabin-Karp 完整实现

def rabin_karp_search(text, pattern):
    """Rabin-Karp 字符串匹配（滚动哈希 + 逐字符验证）
    平均 O(n+m)，最坏 O(nm)（哈希冲突）
    """
    n, m = len(text), len(pattern)
    if m > n or m == 0:
        return [] if m > n else [0]

    base = 256        # 字符集大小
    mod = 10**9 + 7   # 大质数

    # 预计算 base^(m-1) mod mod
    h = pow(base, m - 1, mod)

    # 计算初始哈希
    pattern_hash = 0
    window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    result = []
    for i in range(n - m + 1):
        # 哈希匹配后逐字符验证（防冲突）
        if pattern_hash == window_hash and text[i:i + m] == pattern:
            result.append(i)
        # 滚动哈希
        if i < n - m:
            window_hash = (window_hash - ord(text[i]) * h) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            window_hash = (window_hash + mod) % mod  # 保证非负

    return result

# 示例
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
print(rabin_karp_search(text, pattern))  # [0, 10]

7.3 双模数哈希防冲突

def rabin_karp_double_hash(text, pattern):
    """双模数 Rabin-Karp：极大降低冲突概率"""
    n, m = len(text), len(pattern)
    if m > n:
        return []

    base = 256
    mod1, mod2 = 10**9 + 7, 10**9 + 9  # 双质数

    h1 = pow(base, m - 1, mod1)
    h2 = pow(base, m - 1, mod2)

    ph1 = ph2 = wh1 = wh2 = 0
    for i in range(m):
        ph1 = (ph1 * base + ord(pattern[i])) % mod1
        ph2 = (ph2 * base + ord(pattern[i])) % mod2
        wh1 = (wh1 * base + ord(text[i])) % mod1
        wh2 = (wh2 * base + ord(text[i])) % mod2

    result = []
    for i in range(n - m + 1):
        if ph1 == wh1 and ph2 == wh2:
            result.append(i)
        if i < n - m:
            wh1 = ((wh1 - ord(text[i]) * h1) * base + ord(text[i + m])) % mod1
            wh2 = ((wh2 - ord(text[i]) * h2) * base + ord(text[i + m])) % mod2
            wh1 = (wh1 + mod1) % mod1
            wh2 = (wh2 + mod2) % mod2

    return result

# 示例
print(rabin_karp_double_hash("ABABDABACDABABCABAB", "ABAB"))  # [0, 2, 12]

7.4 C++ 实现

#include <vector>
#include <string>
using namespace std;
typedef long long ll;

// Rabin-Karp 单模数实现
vector<int> rabinKarpSearch(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (m > n || m == 0) return m == 0 ? vector<int>{0} : vector<int>{};

    const ll base = 256;
    const ll mod = 1000000007;
    ll h = 1;
    for (int i = 0; i < m - 1; ++i) h = h * base % mod;

    ll ph = 0, wh = 0;
    for (int i = 0; i < m; ++i) {
        ph = (ph * base + (unsigned char)pattern[i]) % mod;
        wh = (wh * base + (unsigned char)text[i]) % mod;
    }

    vector<int> result;
    for (int i = 0; i <= n - m; ++i) {
        if (ph == wh && text.substr(i, m) == pattern) {
            result.push_back(i);
        }
        if (i < n - m) {
            wh = ((wh - (unsigned char)text[i] * h) % mod * base
                  + (unsigned char)text[i + m]) % mod;
            wh = (wh + mod) % mod;  // 关键：保证非负
        }
    }
    return result;
}

7.5 多模式 Rabin-Karp

def multi_pattern_rabin_karp(text, patterns):
    """多模式 Rabin-Karp：同时匹配多个模式串
    适用于模式串长度相同的场景
    """
    if not patterns:
        return {}
    m = len(patterns[0])
    base = 256
    mod = 10**9 + 7

    # 预处理所有模式串的哈希
    pattern_hashes = {}
    for p in patterns:
        if len(p) != m:
            raise ValueError("所有模式串长度必须相同")
        h = 0
        for ch in p:
            h = (h * base + ord(ch)) % mod
        pattern_hashes.setdefault(h, []).append(p)

    h_pow = pow(base, m - 1, mod)
    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * base + ord(text[i])) % mod

    result = {p: [] for p in patterns}
    for i in range(len(text) - m + 1):
        if window_hash in pattern_hashes:
            for p in pattern_hashes[window_hash]:
                if text[i:i + m] == p:
                    result[p].append(i)
        if i < len(text) - m:
            window_hash = (window_hash - ord(text[i]) * h_pow) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            window_hash = (window_hash + mod) % mod

    return result

# 示例
text = "ABABDABACDABABCABAB"
patterns = ["ABAB", "CDAB", "XYZ"]
print(multi_pattern_rabin_karp(text, patterns))
# {'ABAB': [0, 2, 12], 'CDAB': [7, 11], 'XYZ': []}

第 8 章 Boyer-Moore 算法

8.1 Boyer-Moore 核心思想

Boyer-Moore 算法（由 Robert S. Boyer 与 J. Strother Moore 于 1977 年在 Communications of the ACM 第 20 卷第 10 期发表论文《A fast string searching algorithm》提出）从右向左扫描模式串，结合两条启发式规则跳过不可能匹配的位置：

1. 坏字符规则（bad character rule）：失配时，根据主串中失配字符在模式串中的位置决定跳跃。
2. 好后缀规则（good suffix rule）：根据已匹配的后缀决定跳跃。

8.2 坏字符规则

def build_bad_char_table(pattern):
    """构建坏字符表：记录每个字符在模式串中最右出现位置"""
    bad_char = {}
    for i, ch in enumerate(pattern):
        bad_char[ch] = i
    return bad_char

def boyer_moore_bad_char(text, pattern):
    """仅使用坏字符规则的 Boyer-Moore"""
    n, m = len(text), len(pattern)
    if m == 0:
        return [0]
    bad_char = build_bad_char_table(pattern)
    result = []
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and text[i + j] == pattern[j]:
            j -= 1
        if j < 0:
            result.append(i)
            # 移动到下一个可能位置
            next_ch = text[i + m] if i + m < n else ''
            i += m - bad_char.get(next_ch, -1)
        else:
            # 坏字符 text[i+j] 在模式串中最右位置
            bc_pos = bad_char.get(text[i + j], -1)
            shift = max(1, j - bc_pos)
            i += shift
    return result

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(boyer_moore_bad_char(text, pattern))  # [10]

8.3 好后缀规则

def build_good_suffix_table(pattern):
    """构建好后缀表"""
    m = len(pattern)
    good_suffix = [m] * m  # 默认移动 m
    # suffix[i] = 模式串末尾与位置 i 结尾的子串的最长公共后缀长度
    suffix = [0] * m
    suffix[m - 1] = m
    g = m - 1
    f = 0
    for i in range(m - 2, -1, -1):
        if i > g and suffix[i + m - 1 - f] < i - g:
            suffix[i] = suffix[i + m - 1 - f]
        else:
            if i < g:
                g = i
            f = i
            while g >= 0 and pattern[g] == pattern[g + m - 1 - f]:
                g -= 1
            suffix[i] = f - g

    # 计算好后缀表
    for i in range(m):
        good_suffix[i] = m
    j = 0
    for i in range(m - 1, -1, -1):
        if suffix[i] == i + 1:
            for ; j < m - 1 - i; j++:
                if good_suffix[j] == m:
                    good_suffix[j] = m - 1 - i
    for i in range(m - 1):
        good_suffix[m - 1 - suffix[i]] = m - 1 - i
    return good_suffix

注：好后缀表构建较复杂，实践中常仅使用坏字符规则（Boyer-Moore-Horspool 变体）。

8.4 完整 Boyer-Moore 实现

def boyer_moore_search(text, pattern):
    """完整 Boyer-Moore：坏字符 + 好后缀"""
    n, m = len(text), len(pattern)
    if m == 0:
        return [0]

    # 坏字符表
    bad_char = {}
    for i, ch in enumerate(pattern):
        bad_char[ch] = i

    # 好后缀表（简化版）
    good_suffix = [0] * m
    for i in range(m):
        good_suffix[i] = m

    result = []
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and text[i + j] == pattern[j]:
            j -= 1
        if j < 0:
            result.append(i)
            # 匹配后移动
            next_ch = text[i + m] if i + m < n else ''
            i += m - bad_char.get(next_ch, -1)
        else:
            # 坏字符移动
            bc_shift = j - bad_char.get(text[i + j], -1)
            # 好后缀移动（简化处理）
            gs_shift = good_suffix[j] if j < m - 1 else 1
            i += max(1, bc_shift, gs_shift)
    return result

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(boyer_moore_search(text, pattern))  # [10]