算法简介
什么是KMP算法？
KMP算法是一种高效的字符串匹配算法，由Knuth、Morris和Pratt三人共同提出，因此得名。它用于在一个文本串（Text）中查找一个模式串（Pattern）的出现位置，时间复杂度可达O(n + m)，其中n是文本串长度，m是模式串长度。
传统暴力匹配的问题
暴力匹配在每次失配时，文本指针和模式指针都要回溯，导致时间复杂度为O(n×m)。例如：
文本：ABCABCDABABCDABCDABDE
模式：ABCDABD
暴力匹配会进行多次不必要的回溯，效率低下
KMP算法的核心改进
KMP算法通过预处理模式串，构建前缀函数（部分匹配表），在失配时避免文本指针回溯，仅调整模式指针位置，从而大幅提高效率。
关键思想：利用已匹配的信息，确定模式串中可以直接跳过的部分
应用场景
文本编辑器中的查找功能
搜索引擎的关键词匹配
语法分析器中的模式识别
生物信息学中的基因序列匹配
网络入侵检测中的特征匹配
自然语言处理中的模式匹配
前缀函数（Prefix Function）
什么是前缀函数？
前缀函数是KMP算法的核心，对于模式串P[0..m-1]，前缀函数π[i]定义为：
π[i]是模式串P[0..i]的最长前缀（不等于自身）同时也是后缀的长度
术语解释
- 前缀：从字符串开头开始的子串（不包含最后一个字符）
- 后缀：以字符串结尾的子串（不包含第一个字符）
- 最长公共前缀后缀：同时是前缀和后缀的最长子串
示例：模式串 "ABABC"
| i | P[0..i] | 最长公共前缀后缀 | π[i] |
|---|---|---|---|
| 0 | A | 无 | 0 |
| 1 | AB | 无 | 0 |
| 2 | ABA | A | 1 |
| 3 | ABAB | AB | 2 |
| 4 | ABABC | 无 | 0 |
前缀函数的计算方法
前缀函数可以通过迭代方式高效计算，时间复杂度为O(m)。基本思想是利用已计算的前缀函数值来计算当前值：
计算步骤
- 初始化π[0] = 0（单个字符没有前缀和后缀）
- 对于i从1到m-1：
- 令k = π[i-1]
- 若P[i] == P[k]，则π[i] = k + 1
- 否则，令k = π[k-1]，重复检查，直到k=0
- 若仍不匹配，则π[i] = 0
计算代码
// 计算模式串的前缀函数
vector<int> computePrefixFunction(const string& pattern) {
int m = pattern.size();
vector<int> pi(m, 0); // 前缀函数数组
for (int i = 1; i < m; i++) {
int k = pi[i-1]; // 从之前的前缀函数值开始
// 不匹配时，回溯到更短的前缀
while (k > 0 && pattern[i] != pattern[k]) {
k = pi[k-1];
}
// 如果匹配，延长前缀长度
if (pattern[i] == pattern[k]) {
k++;
}
pi[i] = k;
}
return pi;
}KMP匹配过程
匹配算法原理
KMP匹配过程使用前缀函数来避免文本指针回溯，仅通过调整模式指针实现高效匹配。基本步骤如下：
-
初始化
设i为文本指针（初始0），j为模式指针（初始0）
-
匹配推进
当文本和模式字符匹配（text[i] == pattern[j]），i和j同时加1
-
匹配成功
当j == m（模式长度），找到匹配位置（i - j），然后调整j = π[j-1]继续查找
-
匹配失败
当text[i] != pattern[j]：
- 若j > 0，设置j = π[j-1]（利用前缀函数回溯）
- 若j == 0，设置i = i + 1（文本指针后移）
核心优势
文本指针i始终向前移动，从不回溯，保证了算法的线性时间复杂度
匹配过程示例
以文本"ABABABC"和模式"ABABC"为例，展示KMP匹配过程：
步骤1：初始状态
文本: A B A B A B C
i=0
模式: A B A B C
j=0
A == A，i=1，j=1
步骤2：前4个字符匹配
文本: A B A B A B C
i=4
模式: A B A B C
j=4
A != C，失配。根据前缀函数π[3]=2，设置j=2
步骤3：调整后继续匹配
文本: A B A B A B C
i=4
模式: A B A B C
j=2
A == A，i=5，j=3。继续匹配直到j=5（模式长度），找到匹配位置i-j=2
完整代码实现
KMP算法完整实现
以下是KMP算法的完整C++实现，包括前缀函数计算和模式匹配两个核心部分：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
/**
* 计算模式串的前缀函数
* @param pattern 模式字符串
* @return 前缀函数数组
*/
vector<int> computePrefixFunction(const string& pattern) {
int m = pattern.size();
vector<int> pi(m, 0); // 前缀函数数组，初始化为0
for (int i = 1; i < m; i++) {
int k = pi[i-1]; // 从之前的前缀函数值开始
// 不匹配时，回溯到更短的前缀
while (k > 0 && pattern[i] != pattern[k]) {
k = pi[k-1];
}
// 如果匹配，延长前缀长度
if (pattern[i] == pattern[k]) {
k++;
}
pi[i] = k;
}
return pi;
}
/**
* KMP模式匹配算法
* @param text 文本字符串
* @param pattern 模式字符串
* @return 所有匹配位置的起始索引列表
*/
vector<int> kmpSearch(const string& text, const string& pattern) {
vector<int> result; // 存储所有匹配位置
int n = text.size();
int m = pattern.size();
// 边界条件处理
if (m == 0 || n < m) {
return result;
}
// 计算前缀函数
vector<int> pi = computePrefixFunction(pattern);
int i = 0; // 文本指针
int j = 0; // 模式指针
while (i < n) {
// 字符匹配，移动两个指针
if (text[i] == pattern[j]) {
i++;
j++;
}
// 找到一个匹配
if (j == m) {
result.push_back(i - j); // 记录匹配起始位置
j = pi[j - 1]; // 继续查找下一个匹配
}
// 字符不匹配
else if (i < n && text[i] != pattern[j]) {
// j不为0时，利用前缀函数回溯
if (j != 0) {
j = pi[j - 1];
}
// j为0时，移动文本指针
else {
i++;
}
}
}
return result;
}
// 示例用法
int main() {
string text = "ABABABCABABABCDABDE";
string pattern = "ABABC";
vector<int> matches = kmpSearch(text, pattern);
if (matches.empty()) {
cout << "未找到匹配的模式串" << endl;
} else {
cout << "模式串 \"" << pattern << "\" 在文本中出现的位置为：" << endl;
for (int pos : matches) {
cout << "位置 " << pos << "：";
cout << text.substr(pos, pattern.size()) << endl;
}
}
return 0;
}代码说明
- computePrefixFunction：计算模式串的前缀函数数组
- kmpSearch：实现KMP匹配算法，返回所有匹配位置
- 时间复杂度：O(n + m)，其中n是文本长度，m是模式长度
- 空间复杂度：O(m)，主要用于存储前缀函数数组
- 支持查找所有匹配位置，而非仅第一个匹配
实例解析
实例1：基础匹配
输入：
文本："ABC ABCDAB ABCDABCDABDE"
模式："ABCDABD"
前缀函数计算：
模式 "ABCDABD" 的前缀函数为：
π = [0, 0, 0, 0, 1, 2, 0]
输出：
匹配位置：15
匹配内容："ABCDABD"
解析：
该例展示了KMP算法的基本功能，在较长文本中准确找到模式串的位置。相比暴力匹配的多次回溯，KMP仅通过前缀函数调整模式指针，效率更高。
实例2：多匹配情况
输入：
文本："ABABABAABABABAC"
模式："ABABA"
前缀函数计算：
模式 "ABABA" 的前缀函数为：
π = [0, 0, 1, 2, 3]
输出：
匹配位置：0、2
匹配内容："ABABA"（位置0-4）、"ABABA"（位置2-6）
解析：
该例展示了模式串在文本中多次出现的情况，特别是重叠出现的情况。KMP算法能够高效找到所有匹配位置，包括重叠的匹配。
练习题
1. 计算前缀函数
计算模式串 "ABCABCD" 的前缀函数数组。
提示：
按照前缀函数定义，逐步计算每个位置的最长公共前缀后缀长度
2. KMP匹配过程
已知文本为 "ABACABADABACABA"，模式为 "ABACABA"，请手动模拟KMP匹配过程，找出所有匹配位置。
提示：
先计算模式串的前缀函数，再按照KMP匹配步骤逐步推进
3. 算法应用
实现一个函数，使用KMP算法统计模式串在文本中出现的次数。
提示：
基于基本KMP算法，每次找到匹配时计数器加1即可