1. 概述
在字符串匹配领域，我们有多种搜索算法。本文将介绍 KMP（Knuth-Morris-Pratt）算法，它用于在一个较长的文本 T 中查找模式串 W 的所有出现位置。
我们会先回顾一下 暴力搜索（Naive Search） 的实现方式和问题所在，接着讲解 KMP 的核心思想：LPS（最长前缀后缀数组），并结合伪代码说明其实现细节。最后通过一个示例帮助理解整个流程。
2. 暴力搜索算法
暴力搜索非常直观：**从文本 T 的每一个位置开始尝试匹配模式串 W**。
伪代码如下：
algorithm NaiveSearch(W, T, m, n):
for i <- 0 to n - m:
ok <- true
for j <- 0 to m - 1:
if W[j] != T[i + j]:
ok <- false
break
if ok:
return true
return false
示例分析
假设 W = "aab"，T = "aaaab"，暴力搜索的匹配过程如下：
| 步骤 | 比较内容 | 结果 |
|---|---|---|
| i=0 | a a a a b | a a b ❌ |
| i=1 | a a a a b | a a b ❌ |
| i=2 | a a a a b | a a b ✅ |
缺陷分析 ✅❌
- 重复比较：在
i=1和i=2的比较中，前面已经匹配的部分（如 "aa"）被反复检查。 - 时间复杂度：
O(n * m)，其中n是文本长度，m是模式串长度。
3. KMP 算法原理
KMP 的关键在于 利用模式串自身的信息跳过不必要的重复比较。它通过预处理模式串得到 LPS 数组，在匹配失败时指导跳转位置。
3.1. 前缀与后缀定义
在讲解 LPS 前，先明确几个术语：
| 术语 | 定义 |
|---|---|
| 前缀（Prefix） | 从字符串开头开始的任意子串，不包括整个字符串本身（即 Proper Prefix） |
| 后缀（Suffix） | 从字符串结尾开始的任意子串，不包括整个字符串本身（即 Proper Suffix） |
| LPS | Longest Proper Prefix which is also a Proper Suffix，即最长公共前后缀 |
3.2. LPS 数组构造
LPS 数组的构造是 KMP 的核心。我们以 W = "aabaaba" 为例，构造其 LPS 数组如下：
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| W | a | a | b | a | a | b | a | |
| LPS | -1 | 0 | 1 | 0 | 1 | 2 | 3 | 4 |
构造算法如下：
algorithm CalculateLPS(W, m):
i <- 0
j <- -1
LPS <- array of size m + 1
LPS[0] <- -1
while i < m:
while j >= 0 and W[i] != W[j]:
j <- LPS[j]
i <- i + 1
j <- j + 1
LPS[i] <- j
return LPS
时间复杂度分析
- 构造 LPS 数组的时间复杂度为
O(m)，其中m是模式串长度。 - 每次比较失败时，
j会回退到LPS[j]，但整体上i和j都只前进一次。
3.3. KMP 匹配过程
有了 LPS 数组后，KMP 的匹配逻辑如下：
algorithm KMPSearch(W, T, m, n, LPS):
i <- 0
j <- 0
while i < n:
while j >= 0 and T[i] != W[j]:
j <- LPS[j]
i <- i + 1
j <- j + 1
if j == m:
return true
return false
核心思想
- 匹配成功：
j++ - 匹配失败：
j = LPS[j]，即回退到当前已匹配部分的最长公共前后缀位置 - 时间复杂度：
O(n)，其中n是文本长度
总体时间复杂度
- 构造 LPS：
O(m) - 执行匹配：
O(n) - 总复杂度：
O(n + m)
4. 示例演示
我们用一个具体例子来演示 KMP 的运行过程：
T = "aaaab"W = "aab"
LPS 表
| index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| W | a | a | b | |
| LPS | -1 | 0 | 1 | 0 |
匹配过程
| 步骤 | i | j | 当前字符 | 匹配状态 | 说明 |
|---|---|---|---|---|---|
| 1 | 0 | 0 | T[0]=a, W[0]=a | ✅ | j=1 |
| 2 | 1 | 1 | T[1]=a, W[1]=a | ✅ | j=2 |
| 3 | 2 | 2 | T[2]=a, W[2]=b | ❌ | j=LPS[2]=1 |
| 4 | 2 | 1 | T[2]=a, W[1]=a | ✅ | j=2 |
| 5 | 3 | 2 | T[3]=a, W[2]=b | ❌ | j=LPS[2]=1 |
| 6 | 3 | 1 | T[3]=a, W[1]=a | ✅ | j=2 |
| 7 | 4 | 2 | T[4]=b, W[2]=b | ✅ | j=3，匹配完成 |
✅ 最终匹配成功，W 出现在 T 中。
5. 总结
KMP 算法通过预处理模式串构建 LPS 数组，有效避免了暴力搜索中大量的重复比较。其核心优势在于：
- 时间复杂度低：
O(n + m) - 适用于重复子串较多的模式匹配场景
- 适用于需要多次匹配的场景（如正则表达式、文本编辑器等）
虽然实现略复杂，但其性能优势在大数据量匹配中尤为突出。掌握 KMP 是理解字符串匹配算法进阶的重要一步。