Day 17
kmp
KMP (Knuth-Morris-Pratt) 算法是一种高效的字符串匹配算法，用于在一个主字符串（文本 T）中查找一个模式字符串（P）的出现位置。
与朴素的暴力匹配算法相比，KMP 算法通过一个巧妙的预处理步骤，避免了不必要的字符比较，从而将时间复杂度从 O (N*M) 降低到了 O (N+M)，其中 N 是文本长度，M 是模式长度。
1. 核心思想
KMP 算法的核心思想是利用已经匹配过的信息，避免主串指针的回溯。
让我们通过一个例子来理解朴素算法的低效之处：
- 文本 T:
BBC ABCDAB ABCDABCDABDE - 模式 P:
ABCDABD
朴素算法的过程：
- BBC ABCDAB ABCDABCDABDEABCDABD^B 和 A 不匹配，模式右移一位。
- BBC ABCDAB ABCDABCDABDEABCDABD^B 和 A 不匹配，模式右移一位。
- BBC ABCDAB ABCDABCDABDEABCDABD^C 和 A 不匹配，模式右移一位。
- BBC ABCDAB ABCDABCDABDEABCDABD^和 A 不匹配，模式右移一位。
- BBC ABCDAB ABCDABCDABDEABCDABD^A 和 A 匹配，继续比较。
- BBC ABCDAB ABCDABCDABDEABCDABD^B 和 B 匹配，继续比较。
- BBC ABCDAB ABCDABCDABDEABCDABD^C 和 C 匹配，继续比较。
- BBC ABCDAB ABCDABCDABDEABCDABD^D 和 D 匹配，继续比较。
- BBC ABCDAB ABCDABCDABDEABCDABD^A 和 A 匹配，继续比较。
- BBC ABCDAB ABCDABCDABDEABCDABD^B 和 B 匹配，继续比较。
- BBC ABCDAB ABCDABCDABDEABCDABD^和 D 不匹配！
此时，朴素算法会将模式右移一位，然后主串指针 i 回溯到 i-j+1 的位置，模式指针 j 重置为 0，重新开始比较：
BBC ABCDAB ABCDABCDABDEABCDABD^这个过程非常低效，因为我们已经知道AB是匹配的，但又要重新比较。
KMP 算法的改进：
当第 11 步发生不匹配时，KMP 算法不会让主串指针 i 回溯。它会利用已经匹配的前缀 ABCDAB 的信息，直接将模式串 P 向右滑动一段距离，然后从模式的某个位置开始继续与主串的当前位置 i 进行比较。
2. 关键概念：部分匹配表 (Partial Match Table, PMT) 或最长公共前后缀 (Longest Prefix Suffix, LPS)
为了实现上述的 “智能滑动”，KMP 算法首先会对模式串 P 进行预处理，生成一个辅助数组，通常称为 next 数组（或 lps 数组）。
next[j] 的定义：对于模式串 P 的前 j+1 个字符组成的子串 P[0...j]，其最长相等的真前缀和真后缀的长度。
- 前缀 (Prefix)：除最后一个字符外，字符串的所有头部子串。例如，
"ABCD"的前缀是["A", "AB", "ABC"]。 - 后缀 (Suffix)：除第一个字符外，字符串的所有尾部子串。例如，
"ABCD"的后缀是["D", "CD", "BCD"]。 - 真 (Proper)：指不等于字符串本身的子串。
示例：计算模式 P = "ABCDABD" 的 next 数组
P[0...0] = "A": 没有真前缀和真后缀，next[0] = 0。P[0...1] = "AB": 前缀["A"]，后缀["B"]。无公共部分，next[1] = 0。P[0...2] = "ABC": 前缀["A", "AB"]，后缀["C", "BC"]。无公共部分，next[2] = 0。P[0...3] = "ABCD": 前缀["A", "AB", "ABC"]，后缀["D", "CD", "BCD"]。无公共部分，next[3] = 0。P[0...4] = "ABCDA": 前缀["A", "AB", "ABC", "ABCD"]，后缀["A", "DA", "CDA", "BCDA"]。最长公共部分是"A"，长度为 1。next[4] = 1。P[0...5] = "ABCDAB": 前缀["A", "AB", "ABC", "ABCD", "ABCDA"]，后缀["B", "AB", "DAB", "CDAB", "BCDAB"]。最长公共部分是"AB"，长度为 2。next[5] = 2。P[0...6] = "ABCDABD": 前缀["A", "AB", ..., "ABCDAB"]，后缀["D", "BD", ..., "BCDABD"]。无公共部分，next[6] = 0。
所以，模式 "ABCDABD" 的 next 数组为：[0, 0, 0, 0, 1, 2, 0]。
3. 算法步骤
KMP 算法分为两步：
- 构建
next数组。 - 利用
next数组进行匹配。
步骤一：构建 next 数组
这是一个递推的过程。
cpp
运行
// s 是模式串
void buildNext(const string& s, vector<int>& next) {
int n = s.size();
next.resize(n, 0);
int j = 0; // j 指向前缀的末尾
// i 从 1 开始，指向后缀的末尾
for (int i = 1; i < n; ++i) {
// 情况1：s[i] != s[j]，回退 j
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
// 情况2：s[i] == s[j]，匹配成功，j 前进
if (s[i] == s[j]) {
j++;
}
// 更新 next[i]
next[i] = j;
}
}
步骤二：利用 next 数组进行匹配
cpp
运行
// t 是文本串, p 是模式串, next 是模式串的 next 数组
int kmpSearch(const string& t, const string& p, const vector<int>& next) {
int n = t.size();
int m = p.size();
int j = 0; // j 是模式串的指针
// i 是文本串的指针，它不会回退
for (int i = 0; i < n; ++i) {
// 情况1：t[i] != p[j]，利用 next 数组回退模式串指针 j
while (j > 0 && t[i] != p[j]) {
j = next[j - 1];
}
// 情况2：t[i] == p[j]，匹配成功，j 前进
if (t[i] == p[j]) {
j++;
}
// 情况3：j == m，说明模式串完全匹配
if (j == m) {
// 返回匹配的起始索引
return i - m + 1;
}
}
// 未找到匹配
return -1;
}
4. C++ 完整实现
cpp
运行
#include <iostream>
#include <vector>
#include <string>
using namespace std;
/**
* @brief 构建 KMP 算法的 next 数组 (最长公共前后缀数组)
* @param pattern 模式串
* @param next 用于存储结果的 next 数组
*/
void buildNext(const string& pattern, vector<int>& next) {
int n = pattern.size();
next.resize(n, 0);
int j = 0; // j 指向前缀的末尾
// i 从 1 开始，指向后缀的末尾
for (int i = 1; i < n; ++i) {
// 1. 当 pattern[i] != pattern[j] 时，回退 j
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
// 2. 当 pattern[i] == pattern[j] 时，j 前进
if (pattern[i] == pattern[j]) {
j++;
}
// 3. 更新 next[i]
next[i] = j;
}
}
/**
* @brief 使用 KMP 算法在文本串中查找模式串
* @param text 文本串
* @param pattern 模式串
* @return int 如果找到，返回第一个匹配的起始索引；否则返回 -1
*/
int kmpSearch(const string& text, const string& pattern) {
int n = text.size();
int m = pattern.size();
if (m == 0) return 0;
if (n < m) return -1;
vector<int> next;
buildNext(pattern, next);
int j = 0; // j 是模式串的指针
// i 是文本串的指针，它不会回退
for (int i = 0; i < n; ++i) {
// 1. 当 text[i] != pattern[j] 时，利用 next 数组回退模式串指针 j
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1];
}
// 2. 当 text[i] == pattern[j] 时，j 前进
if (text[i] == pattern[j]) {
j++;
}
// 3. 如果 j == m，说明模式串完全匹配
if (j == m) {
// 返回匹配的起始索引
return i - m + 1;
}
}
// 遍历完文本串仍未找到匹配
return -1;
}
int main() {
string text = "BBC ABCDAB ABCDABCDABDE";
string pattern = "ABCDABD";
cout << "文本串: " << text << endl;
cout << "模式串: " << pattern << endl;
cout << "---------------------------------" << endl;
vector<int> next;
buildNext(pattern, next);
cout << "模式串 \"" << pattern << "\" 的 next 数组为: ";
for (int val : next) {
cout << val << " ";
}
cout << endl << "---------------------------------" << endl;
int index = kmpSearch(text, pattern);
if (index != -1) {
cout << "匹配成功！" << endl;
cout << "模式串在文本串中的起始索引为: " << index << endl;
cout << "匹配的子串是: " << text.substr(index, pattern.size()) << endl;
} else {
cout << "匹配失败，文本串中未找到模式串。" << endl;
}
return 0;
}
运行结果
plaintext
文本串: BBC ABCDAB ABCDABCDABDE 模式串: ABCDABD --------------------------------- 模式串 "ABCDABD" 的 next 数组为: 0 0 0 0 1 2 0 --------------------------------- 匹配成功！ 模式串在文本串中的起始索引为: 15 匹配的子串是: ABCDABD
总结
- KMP 算法通过预处理模式串生成
next数组，实现了在字符串匹配时主串指针不回溯，从而大大提高了匹配效率。 next数组的核心是最长公共前后缀 (LPS)，它告诉我们当匹配失败时，模式串应该向右滑动多远，以及从哪个位置开始下一次比较。- 时间复杂度：预处理
next数组为 O (M)，匹配过程为 O (N)，总时间复杂度为 O (N+M)。 - 空间复杂度：主要由
next数组决定，为 O (M)。
