KMP算法通过构建next数组实现高效字符串匹配，避免主串指针回溯，时间复杂度O(n+m)；next数组记录模式串各位置最长相等真前后缀长度，用于失配时确定模式串的滑动位置；例如模式串"ABABC"的next数组为[0,0,1,2,0]；匹配过程中，当字符不匹配且j>0时，j回退到next[j-1]，否则i++；最终输出所有匹配起始位置，如主串"ABABDABACDABABCABC"中找到"ABABC"在位置8匹配。
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主串（文本串）中查找一个子串（模式串）的出现位置。与暴力匹配相比，KMP避免了主串指针的回溯，时间复杂度为 O(n + m)，其中 n 是主串长度，m 是模式串长度。
核心思想：利用部分匹配表（Next数组）
KMP 的关键在于预处理模式串，构建一个 next 数组（也叫失败函数或部分匹配表），记录模式串每个位置之前的最长相等真前后缀长度。当匹配失败时，利用 next 数组决定模式串应该跳到哪个位置继续匹配，而不是从头开始。
举个例子：
模式串 "ABABC" 的 next 数组为 [0, 0, 1, 2, 0]。解释如下：
立即学习“C++免费学习笔记（深入）”；
- next[0] = 0（单个字符无前后缀）
- next[1] = 0（"AB" 无公共前后缀）
- next[2] = 1（"ABA" 中前缀 "A" 和后缀 "A" 相同）
- next[3] = 2（"ABAB" 中前缀 "AB" 和后缀 "AB" 相同）
- next[4] = 0（"ABABC" 无公共前后缀）
构建 Next 数组（预处理）
使用双指针法构造 next 数组，类似于在模式串自己和自己做匹配：
void getNext(const string& pattern, vector<int>& next) {
int m = pattern.length();
next.resize(m);
next[0] = 0;
int len = 0; // 当前最长相等前后缀长度
int i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
next[i] = len;
i++;
} else {
if (len != 0) {
len = next[len - 1]; // 回退 len
} else {
next[i] = 0;
i++;
}
}
}
}KMP 匹配过程
主串和模式串进行匹配，当字符不相等时，利用 next 数组移动模式串指针：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// KMP 主函数，返回所有匹配位置
vector<int> kmpSearch(const string& text, const string& pattern) {
vector<int> result;
int n = text.length();
int m = pattern.length();
if (m == 0) return result;
vector<int> next;
getNext(pattern, next);
int i = 0; // text 指针
int j = 0; // pattern 指针
while (i < n) {
if (text[i] == pattern[j]) {
i++;
j++;
}
if (j == m) {
result.push_back(i - j); // 找到一次匹配
j = next[j - 1];
} else if (i < n && text[i] != pattern[j]) {
if (j != 0) {
j = next[j - 1];
} else {
i++;
}
}
}
return result;
}完整可运行示例
```cpp int main() { string text = "ABABDABACDABABCABC"; string pattern = "ABABC";vector<int> matches = kmpSearch(text, pattern);
if (matches.empty()) {
cout << "未找到匹配" << endl;
} else {
cout << "模式串在以下位置匹配: ";
for (int pos : matches) {
cout << pos << " ";
}
cout << endl;
}
return 0;}
<strong>输出结果：</strong> <p>模式串在以下位置匹配: 8</p> <H3>总结与注意事项</H3> <p>KMP 算法的核心优势是主串指针不回退，适合处理大文本搜索。理解 next 数组的含义至关重要 —— 它保存的是“当匹配失败时，模式串应跳转到的位置”。</p> <p>注意点：</p> <ul> <li>next 数组构建时，本质是 pattern 自匹配</li> <li>匹配过程中，j 回退到 next[j-1] 而不是 next[j]</li> <li>若只需找第一个匹配，可在找到后立即返回</li> </ul> 基本上就这些，掌握 next 数组的逻辑是理解 KMP 的关键。
