Part 6.1：KMP 算法
引言：智能的 Ctrl+F
在日常使用电脑时，Ctrl+F 是我们用得最多的功能之一。当你在一个数万字的文档中查找一个特定单词时，计算机会瞬间定位到它的位置。这个看似简单的操作背后，隐藏着强大的字符串模式匹配 (String Pattern Matching) 算法。
最朴素的想法是什么？——**暴力匹配 (Brute Force)**。将要查找的单词（模式串）与文档（文本串）从头开始，一个字符一个字符地对齐比较。如果遇到不匹配的字符，就将模式串向后移动一位，再从头开始比较。这种方法在大多数情况下工作得不错，但在某些“恶意”的情况下，它的效率会变得极其低下。
例如，在文本串 AAAAAAAAAAAAAAAAAB 中查找模式串 AAAAAB。
Text: A A A A A A A A A A A A A A A B
Pattern:A A A A A B (Mismatch at B)
A A A A A B (Shift 1, mismatch at B)
A A A A A B (Shift 2, mismatch at B)
...每次失败，我们都只是将模式串后移一位，然后又进行大量重复的 A 与 A 的比较。这种“愚蠢”的回溯，正是暴力匹配的性能瓶颈。
KMP 算法（由 Knuth, Morris, Pratt 三位学者在 1977 年共同发表）正是为了解决这个问题而生。它通过预处理模式串，找到其中的“对称性”，使得在匹配失败时，能够智能地、大幅度地向后滑动，而不需要回溯文本串的指针，从而实现了 O(n) 的线性时间复杂度。
为什么 KMP 算法如此重要？
- 面试价值：KMP 是字符串算法的必考点，也是中高级工程师面试的常客。它深刻地体现了“空间换时间”和“利用已有信息”的算法思想，是考察候选人算法思维深度和代码实现能力的经典题目。
- 工程价值：KMP 及其变种是许多文本处理软件、搜索引擎、入侵检测系统、基因序列分析工具的核心组成部分。
本文将带你从零开始，彻底搞懂 KMP 算法的精髓——next 数组。
背景知识：暴力匹配及其缺陷
def brute_force_search(text, pattern):
n, m = len(text), len(pattern)
for i in range(n - m + 1): # i: text 中的起始位置
j = 0
while j < m:
if text[i + j] != pattern[j]:
break
j += 1
if j == m:
return i # 找到匹配
return -1- 时间复杂度：最坏情况下为
O((n-m+1) * m)，约等于O(n*m)。 - 缺陷：文本串的指针
i在每次匹配失败后，都会回溯到i+1，丢失了之前已经匹配上的部分信息。
详细算法原理：KMP 的核心——Next 数组
KMP 算法的核心思想是：当失配发生时，主串 text 的指针 i 永不回溯，而是通过移动模式串 pattern 的指针 j 来实现高效匹配。
而 j 应该移动到哪里，就完全取决于一个预先计算好的 next 数组。
1. 算法的“直觉”：利用已匹配的前缀
假设我们在匹配过程中，text[i] 和 pattern[j] 发生了失配。
text: ... a b c a b d ...
^
i
pattern: a b c a b c
^
j此时，我们已经知道 text 中 i 之前的一段 abcab 和 pattern 的前缀 abcab 是匹配的。暴力匹配会把 pattern 后移一位，然后从头开始比较，这显然是低效的。
KMP 的想法是：我们已经匹配上的 pattern 前缀 abcab，它的最长公共前后缀是什么？
- 前缀：
a,ab,abc,abca - 后缀：
b,ab,cab,bcab - 最长公共前后缀：
ab
这个信息告诉我们，pattern 的开头两个字符 ab 和结尾两个字符 ab 是一样的。由于 text 中 i 之前的部分也等于 abcab，那么 text 中 i 之前的最后两个字符也必然是 ab。
图示：利用公共前后缀进行滑动
text: ... a b c a b d ... pattern: a b c a b c (失配) 已匹配部分： a b c a b 最长公共前后缀： a b 滑动后： text: ... a b c a b d ... pattern: a b c a b c (对齐公共前后缀)
我们直接把 pattern 滑动到其前缀 ab 与 text 中对应的后缀 ab 对齐的位置，然后从 pattern[2]（即 c）继续和 text[i] 比较。整个过程中，text 的指针 i 没有动！
这个“最长公共前后缀的长度”，就是 next 数组要告诉我们的信息。
2. 严谨原理：前缀函数 next 数组
状态定义：
next[j]表示在模式串pattern的子串pattern[0...j]中，其最长相等前后缀的长度。⚠️ 注意：这里的前后缀是真前缀和真后缀，即不包含整个字符串本身。
例子：
pattern = "ababaca"
| j | 子串 p[0...j] | 前缀 | 后缀 | 最长相等前后缀 | next[j] |
|---|---|---|---|---|---|
| 0 | a | ∅ | ∅ | ∅ | 0 |
| 1 | ab | a | b | ∅ | 0 |
| 2 | aba | a, ab | a, ba | a | 1 |
| 3 | abab | a, ab, aba | b, ab, bab | ab | 2 |
| 4 | ababa | … | … | aba | 3 |
| 5 | ababac | … | … | a | 1 |
| 6 | ababaca | … | … | a | 1 |
最终 next 数组为 [0, 0, 1, 2, 3, 1, 1]。
3. 如何计算 next 数组？（DP 思想）
计算 next 数组的过程，本身就是一个“自己匹配自己”的动态规划过程。
假设我们已经求出了 next[0], ..., next[i-1]，现在要求 next[i]。
我们比较 pattern[i] 和 pattern[next[i-1]]。
**如果
pattern[i] == pattern[next[i-1]]**：
这意味着pattern[0...i-1]的最长相等前后缀，后面再跟上一个相同的字符，构成了pattern[0...i]的最长相等前后缀。所以next[i] = next[i-1] + 1。**如果
pattern[i] != pattern[next[i-1]]**：
我们需要缩短前缀的长度，寻找一个更短的、能与pattern[0...i-1]的后缀匹配的前缀。这个“次长”的前缀长度是多少呢？恰好就是next[next[i-1] - 1]！这是一个递归的定义。我们不断地向前回溯，直到找到一个匹配的字符，或者回溯到头。
步骤分解 (Step-by-step)
计算 next 数组
- 初始化：
next数组，next[0] = 0。一个指针j=0（代表前缀的末尾），一个指针i=1（代表后缀的末尾）。 - **遍历
pattern**：i从1到m-1。 - 处理不匹配：当
j > 0且pattern[i] != pattern[j]时，令j = next[j-1]，不断向前回溯。 - 处理匹配：如果
pattern[i] == pattern[j]，则j++。 - 赋值：
next[i] = j。
KMP 匹配
- 初始化：
i=0(文本串指针)，j=0(模式串指针)。 - **遍历
text**：i从0到n-1。 - 处理不匹配：当
j > 0且text[i] != pattern[j]时，令j = next[j-1]，模式串指针向前回溯，文本串指针i不动。 - 处理匹配：如果
text[i] == pattern[j]，则j++。 - 判断成功：如果
j == m，说明匹配成功，返回i - m + 1。然后可以令j = next[j-1]继续寻找下一个匹配。
Python 实现
def compute_next(pattern):
"""计算 KMP 算法的 next 数组"""
m = len(pattern)
next_arr = [0] * m
j = 0 # j: 当前最长公共前后缀的长度
for i in range(1, m):
# 如果不匹配，j 回溯
while j > 0 and pattern[i] != pattern[j]:
j = next_arr[j - 1]
# 如果匹配，j 增加
if pattern[i] == pattern[j]:
j += 1
next_arr[i] = j
return next_arr
def kmp_search(text, pattern):
"""使用 KMP 算法在 text 中查找 pattern"""
n, m = len(text), len(pattern)
if m == 0:
return 0
next_arr = compute_next(pattern)
j = 0 # 模式串的指针
for i in range(n): # 文本串的指针
# 处理不匹配，利用 next 数组回溯 j
while j > 0 and text[i] != pattern[j]:
j = next_arr[j - 1]
# 处理匹配
if text[i] == pattern[j]:
j += 1
# 匹配成功
if j == m:
return i - m + 1
# 如果需要查找所有匹配，则：
# print(f"Found pattern at index {i - m + 1}")
# j = next_arr[j - 1]
return -1
# --- 案例测试 ---
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
next_val = compute_next(pattern)
print(f"Pattern '{pattern}' 的 next 数组是: {next_val}")
# 预期: [0, 0, 1, 2, 0, 1, 2, 3, 4]
start_index = kmp_search(text, pattern)
print(f"在 text 中找到 pattern, 起始索引为: {start_index}") # 预期: 10复杂度推导过程
时间复杂度: O(n + m)
compute_next函数:O(m)。- 外层循环
i从1到m-1，是O(m)。 - 内层
while循环看起来可能多次执行，但j的总增加次数最多为m次，所以j的总减少（回溯）次数也最多为m次。通过均摊分析，while循环的总执行次数是O(m)的。
- 外层循环
kmp_search函数:O(n)。- 外层循环
i从0到n-1，是O(n)。 - 内层
while循环，j的回溯同样可以用均摊分析。i和j都是单调递增的（j的回溯总量受i的前进总量限制）。i前进了n次，所以j的增加总量不超过n次，回溯总量也不超过n次。因此while循环的总执行次数是O(n)的。
- 外层循环
总时间复杂度 = O(m) + O(n) = O(n + m)。
空间复杂度: O(m)
- 我们需要一个
next数组来存储模式串的预处理信息，其长度为m。
优势 / 劣势 / 易错点
优势
- 线性时间：
O(n+m)的时间复杂度，在处理大规模文本和“恶意”数据时效率极高。 - 主串指针不回溯：这使得算法非常适合处理流式数据（stream）。
劣势
- 理解成本高：
next数组的计算过程比较抽象，是 KMP 算法的学习难点。 - 实现稍复杂：相比暴力匹配，代码实现更容易出错。
易错点
next数组的定义：混淆next[j]是长度还是索引。next数组的计算：j = next[j-1]的回溯逻辑是核心，容易写错。- 索引偏移：在实现
next数组时，j和i的关系，以及next[j-1]的使用，很容易出现 off-by-one 错误。
适用场景
- 文本编辑器中的查找功能。
- 搜索引擎中的关键词匹配。
- 入侵检测系统中，匹配已知的攻击模式。
- 生物信息学中，在 DNA 序列中查找特定的基因片段。
- 任何需要高效字符串查找的场景。
总结
KMP 算法通过预处理模式串，挖掘出其自身的结构信息（最长相等前后缀），构建出 next 数组。在匹配过程中，当遇到失配时，它不再是“愚蠢”地将模式串后移一位，而是利用 next 数组进行一次“大跳”，跳过所有不可能匹配成功的位置，从而实现了主串指针不回溯的线性时间匹配。
本文核心要点
✅ 核心思想：利用已匹配部分的“最长相等前后缀”信息，来决定失配后模式串应该滑动多远。
✅ 核心工具：next 数组，next[j] 存储子串 pattern[0...j] 的最长相等前后缀的长度。
✅ 关键操作：失配时，j = next[j-1]，实现模式串指针的快速回溯。
✅ 复杂度：时间 O(n+m)，空间 O(m)。
掌握了 KMP，你就掌握了字符串匹配的精髓。在下一篇文章中，我们将学习另一种强大的字符串数据结构——Trie 树（字典树），看看它是如何高效处理大量字符串前缀查询问题的。