> For the complete documentation index, see [llms.txt](https://datastructure-1.gitbook.io/datastructure-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://datastructure-1.gitbook.io/datastructure-docs/di-san-bu-fen-chuan/04-string-matching-kmp.md). # 第 4 章：字符串匹配（KMP） [<- 第 3 章　栈与队列](/datastructure-docs/di-er-bu-fen-xian-xing-jie-gou/03-stacks-and-queues.md) | [课程目录](/datastructure-docs/readme.md) | [第 5 章　二叉树基础与遍历 ->](/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/05-binary-tree-basics.md) > 所属模块：第三部分：串\ > 对应实现：string\_match.cpp ### 本章导航 * [4.1 字符串匹配问题的本质与暴力匹配的缺陷](#c04-4-1) * [4.2 KMP 算法的哲学飞跃：为什么主串指针绝不回退？](#c04-4-2) * [4.3 前缀函数（Prefix Function）与最长相等真前后缀](#c04-4-3) * [4.3.1 数学定义与几何对称直观](#c04-4-3-1) * [4.3.2 两种主流下标体系对比（算法导论 π 数组 vs 严蔚敏 next 数组）](#c04-4-3-2) * [4.4 线性时间递推求解前缀函数（O(m)）与均摊分析](#c04-4-4) * [4.5 KMP 匹配主循环与不变量证明（O(n)）](#c04-4-5) * [4.6 完整分步手算追踪（Step-by-step Dry Run）](#c04-4-6) * [4.7 失配优化：nextval 数组与消除连环失配](#c04-4-7) * [4.8 工业级单模式匹配算法演进（Boyer-Moore 与 Sunday）](#c04-4-8) * [本章小结](#c04-summary) * [思考题与经典大厂面试题](#c04-exercises) *** ## 第 4 章　字符串匹配（KMP） > 难度：★★★☆☆ | 代码：[string\_match.cpp](https://github.com/Huo0077/DataStructure/blob/main/string_match.cpp) **前置知识**：[第 1 章](/datastructure-docs/di-yi-bu-fen-xu-lun/01-complexity-adt.md) 均摊分析（双指针回退的均摊常数级证明），[第 2 章](/datastructure-docs/di-er-bu-fen-xian-xing-jie-gou/02-linear-list.md) 线性存储。 **学习目标**： 1. 理解朴素字符串匹配在重复模式下退化为 (O(n \cdot m)) 的深层根源； 2. 领悟 KMP 算法“利用模式串自相似性，免除主串指针回溯”的核心思想； 3. 掌握前缀函数（(\pi) 数组 / `next` 数组）的严格数学定义及线性递推构造法； 4. 掌握 `nextval` 优化针对连续重复字符失配的修正机制； 5. 能独立手算任何模式串的 `next` 与 `nextval` 数组。 *** ### 4.1 字符串匹配问题的本质与暴力匹配的缺陷 **问题定义**：给定一个长度为 (n) 的主文本串 (T) 和一个长度为 (m) 的模式串 (P)（(m \le n)），在 (T) 中找出 (P) 首次或所有出现的起始下标。 #### 朴素暴力匹配（Brute-Force, BF） 最直观的解法是双重循环对齐： ```cpp int bruteForce(const string& T, const string& P) { int n = T.size(), m = P.size(); for (int i = 0; i <= n - m; ++i) { int j = 0; while (j < m && T[i + j] == P[j]) { ++j; } if (j == m) return i; // 找到匹配 } return -1; } ``` ``` 主串 T: A A A A A A A A B 模式串 P: A A A B 第 0 轮: A A A [A] != B (比较 4 次失配) 第 1 轮: A A [A] A != B (主串指针 i 回退到 1，再次比对) 第 2 轮: A [A] A A != B ... ``` * **最坏时间复杂度**：(O((n - m + 1) \cdot m) = O(n \cdot m))。在自然语言中字符集大，退化不严重；但在 DNA 序列分析（仅有 A, C, G, T 四种字符）或长重复文本中，暴力匹配将极度缓慢！ * **缺陷本质**：第 0 轮已经知道了 (T\[0..2] == \text{"AAA"})，但在第 1 轮中，算法竟然把已经探测过的信息全部抛弃，让主串指针硬生生倒退回第 1 个位置重新比较！ *** ### 4.2 KMP 算法的哲学飞跃：为什么主串指针绝不回退？ 1977 年，Knuth、Morris 和 Pratt 三位大师联合发表了 KMP 算法。其核心洞见只有一句话： > **“主串指针 (i) 自始至终只进不退，所有回退与位移全由模式串指针 (j) 根据预处理信息独自承担！”** #### 为什么可以不回退？ 假设当前主串在 (T\[i]) 与模式串 (P\[j]) 发生失配： * 这意味着：在此之前，模式串的前 (j) 个字符 (P\[0..j-1]) **已经与主串对应区间 (T\[i-j .. i-1]) 取得了完全一致的匹配**！ * 此时，主串区间的内容已经被模式串的前缀“完全透视”。 * 如果模式串自身有一段“前缀”和“后缀”长得一模一样（自相似性），我们只需将模式串向右滑动，让它的**前缀**直接对齐刚才已经匹配成功的**后缀**，主串指针 (i) 原地不动，继续比较下一个字符即可！ ``` 主串 T: ... [ a b a b ] c ... │ │ │ │ ▲ 模式串 P: [ a b a b ] a ... (在 'c' 与 'a' 处失配, j = 4) └──┘ └──┘ 前缀 后缀 (最长相等前后缀为 "ab", 长度 k = 2) 滑动对齐: ... a b [ a b ] c ... [ a b ] a ... (模式串向右滑动, j 直接跳转到 2 继续比对 'c' 与 'a') ``` *** ### 4.3 前缀函数（Prefix Function）与最长相等真前后缀 #### 4.3.1 数学定义与几何对称直观 定义模式串 (P) 的子串 (P\[0..i]) 的**前缀函数 (\pi\[i])** 为：\ **子串 (P\[0..i]) 的最长相等真前缀（Proper Prefix）与真后缀（Proper Suffix）的长度。** * “真”意味着：前缀或后缀不能等于子串本身（长度严格 (< i + 1)）。 ``` 例如 P = "a b a b a" i = 0: "a" 真前缀: ∅, 真后缀: ∅ => π[0] = 0 i = 1: "a b" 真前缀: "a", 真后缀: "b" => π[1] = 0 i = 2: "a b a" 真前缀: "a", "ab", 真后缀: "a", "ba" => "a"=="a" => π[2] = 1 i = 3: "a b a b" 真前缀: ... 真后缀: ... => "ab"=="ab" => π[3] = 2 i = 4: "a b a b a" 真前缀: ... 真后缀: ... => "aba"=="aba" => π[4] = 3 ``` #### 4.3.2 两种主流下标体系对比（算法导论 π 数组 vs 严蔚敏 next 数组） 国内很多考研和经典教材（严蔚敏版）习惯使用 `next` 数组，而国际竞赛与标准算法（CLRS）使用 (\pi) 数组。初学者极易混淆，二者的映射规则如下： | 模式串索引 (i) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | --------------------------- | :----: | :---: | :---: | :---: | :---: | :---: | :---: | | 字符 (P\[i]) | `a` | `b` | `a` | `b` | `a` | `a` | `b` | | **算法导论 / 力扣 (\pi\[i])** | **0** | **0** | **1** | **2** | **3** | **1** | **2** | | **严蔚敏 0-indexed `next[j]`** | **-1** | **0** | **0** | **1** | **2** | **3** | **1** | | **严蔚敏 1-indexed `next[j]`** | **0** | **1** | **1** | **2** | **3** | **4** | **2** | > **本质映射**：\ > 严蔚敏版的 `next[j]` 表示“当在位置 (j) 失配时，(j) 应该跳转到哪个下标继续比较”。它相当于把 (\pi) 数组**整体右移一位，最左端补 -1**！两者在数学实质上完全等价。 *** ### 4.4 线性时间递推求解前缀函数（O(m)）与均摊分析 若对每个前缀暴力求解最长相等前后缀，整体需要 (O(m^2))。KMP 的神来之笔在于：**用模式串自身与自身匹配，动态规划地在线性 (O(m)) 内求出所有 (\pi\[i])**。 #### 递推推导： 假设已知 (\pi\[0..i-1])，现在要求 (\pi\[i])： * 令候选长度 (j = \pi\[i-1])，它代表了子串 (P\[0..i-1]) 的最长相等前后缀； * 若 (P\[i] == P\[j])，则新字符正好将相等前后缀延长了 1 位：(\pi\[i] = j + 1)； * 若 (P\[i] \ne P\[j])，说明长度为 (j+1) 的匹配宣告破裂。此时我们不能从 0 重新开始，而是退求其次，寻找“次长”的相等前后缀！次长的长度是多少？正是 **(\pi\[j-1])**！我们令 (j = \pi\[j-1])，继续检查 (P\[i]) 是否等于 (P\[j])，直到相等或 (j = 0)。 ```cpp std::vector computePrefixFunction(const std::string& P) { int m = P.size(); std::vector pi(m, 0); int j = 0; // 当前最长匹配前缀的长度 for (int i = 1; i < m; ++i) { // 当字符不匹配且还能向前缩短前缀时，回溯 j while (j > 0 && P[i] != P[j]) { j = pi[j - 1]; } // 如果当前字符匹配成功，前缀长度加 1 if (P[i] == P[j]) { ++j; } pi[i] = j; } return pi; } ``` **为什么复杂度是 (O(m)) 而非 (O(m^2))？** * 在 `for` 循环中，`j` 每次最多增加 1（通过 `++j`）； * `while` 循环中的 `j = pi[j - 1]` 每次至少让 `j` 减小 1； * 因为 `j` 始终非负，所以 `j` 减少的总次数不可能超过增加的总次数（最多 (m-1) 次）！ * 故 `while` 内部操作的总体累计次数 (\le m-1)，均摊到每轮循环为 (O(1))，总时间严格为 (O(m))！ *** ### 4.5 KMP 匹配主循环与不变量证明（O(n)） 有了 (\pi) 数组后，主串匹配的过程与构造前缀函数如出一辙： ```cpp int kmpSearch(const std::string& T, const std::string& P) { int n = T.size(), m = P.size(); if (m == 0) return 0; std::vector pi = computePrefixFunction(P); int j = 0; // 模式串当前匹配到的位置 for (int i = 0; i < n; ++i) { while (j > 0 && T[i] != P[j]) { j = pi[j - 1]; // 主串 i 不变，模式串 j 回跳 } if (T[i] == P[j]) { ++j; } if (j == m) { return i - m + 1; // 匹配成功，返回在主串中的起始下标 } } return -1; // 未找到 } ``` *** ### 4.6 完整分步手算追踪（Step-by-step Dry Run） **示例**： * 主串 (T = \text{"ABABDABACDABABCABAB"}) * 模式串 (P = \text{"ABABCABAB"}) * 经预处理，(P) 的 (\pi) 数组为：`[0, 0, 1, 2, 0, 1, 2, 3, 4]` ``` 【第一阶段：前 4 个字符顺利匹配】 i=0..3: T[0..3] == "ABAB", P[0..3] == "ABAB", j 从 0 增长至 4 【第二阶段：遭遇失配与回跳】 i = 4: T[4] = 'D', P[4] = 'C' ───> 发生失配！ 此时 j = 4, 查表 j = pi[4 - 1] = pi[3] = 2 模式串右移，j 变为 2。 再次比对: T[4] ('D') 与 P[2] ('A') ───> 依然失配！ 查表 j = pi[2 - 1] = pi[1] = 0 模式串再次右移，j 变为 0。 再次比对: T[4] ('D') 与 P[0] ('A') ───> 依然失配！ j 已经为 0 且不匹配，while 退出，本次循环结束。主串指针 i 自增进入 5。 【第三阶段：后续重新推进直至完全匹配】 在 i = 10 之后匹配重新建立，最终在 i = 18 时 j == 9 == m，成功定位起始位置 10！ ``` *** ### 4.7 失配优化：nextval 数组与消除连环失配 尽管经典 KMP 已经非常优秀，但在面对**连续重复字符**时，依然存在不必要的冗余跳转。 #### 连环失配的尴尬： 假设 (P = \text{"AAAA"})，计算其常规 `next` 数组（严蔚敏版）： * `next = [-1, 0, 1, 2]` * 若在 (P\[3] = \text{'A'}) 处与主串字符（比如 `'B'`）失配： 1. 根据 `next[3] = 2`，跳转到 (P\[2]) 去比较； 2. 但 (P\[2]) 也是 `'A'`！既然刚才已经知道 `'B' \ne \text{'A'}`，这次再比必定依然失败！ 3. 接着跳到 (P\[1])，还是 `'A'`，再次失败； 4. 最后跳到 (P\[0])，依然是 `'A'`，再次失败。 #### `nextval` 修正算法： 若退回的目标位置字符与当前失配字符**完全相同**，则当前位置的跳转目标应当**继承**目标位置的 `nextval`： \[ \text{nextval}\[i] = \begin{cases} \text{nextval}\[\text{next}\[i]], & \text{若 } P\[i] == P\[\text{next}\[i]] \ \text{next}\[i], & \text{若 } P\[i] \ne P\[\text{next}\[i]] \end{cases} ] 经过优化后，(P = \text{"AAAA"}) 的 `nextval` 直接变为 `[-1, -1, -1, -1]`，失配时一步到位，彻底根除连环冗余！ *** ### 4.8 工业级单模式匹配算法演进（Boyer-Moore 与 Sunday） 在标准库和工业界文本检索工具（如 GNU `grep`）中，最常用的往往不是 KMP，而是**从后向前匹配的 Boyer-Moore (BM) 算法**或 **Sunday 算法**： * **坏字符规则（Bad Character）**：当末尾字符失配时，根据主串字符在模式串中的最后出现位置，一次性跳过数个乃至整整 (m) 个字符！ * **好后缀规则（Good Suffix）**：与 KMP 的好前缀对称。 * **实际性能**：在长模式串和大规模文本搜索中，BM 算法平均时间复杂度可达 (O(n / m))（亚线性！），远超 KMP 的 (O(n))。 *** ### 本章小结 1. **KMP 的精髓在于利用已有的对称性**：主串指针不回退是效率的根本保障，模式串的前缀自相似性是信息复用的源泉。 2. **前缀函数是动态规划的杰作**：利用已求解的 (\pi\[j-1]) 替代穷举，实现了 (O(m)) 时间的自匹配构造。 3. **均摊分析保证线性上界**：模式串指针的增加与减少次数严格平衡，杜绝了暴力算法的回溯爆炸。 4. **`nextval` 是极致的工程剪枝**：通过识别值等价，避免了连续相同字符上的连环无意义比较。 *** ### 思考题与经典大厂面试题 1. **周期性字符串检测**：给定一个非空的字符串 (s)，检查它是否可以通过由它的一个子串重复多次构成。请证明：若 (s) 具有长度为 (k) 的最小重复周期，则其前缀函数必满足 (\pi\[n-1] > 0) 且 (n \bmod (n - \pi\[n-1]) == 0)。 2. **手算演练**：对于模式串 (P = \text{"abacaba"})，请手工写出其 (\pi) 数组、严蔚敏版 `next` 数组和 `nextval` 数组。 3. **最长回文前缀**：利用 KMP 的前缀函数，如何在 (O(n)) 时间内找到字符串 (s) 的最长回文前缀？（提示：构造辅助串 (s + \text{"#"} + \text{reverse}(s))）。