KMP算法通过构建next数组避免主串指针回退，在O(n+m)时间内完成字符串匹配，核心是利用模式串的最长相等前后缀信息进行跳转，实现高效搜索。
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，能在 O(n + m) 时间内找出模式串在主串中的位置，避免了暴力匹配中不必要的回溯。下面详细讲解其原理并给出 C++ 实现。
核心思想：利用已匹配部分的信息
在暴力匹配中，一旦失配，主串指针会回退，导致重复比较。KMP 的关键是 不回退主串指针，而是根据模式串的结构，移动模式串，跳过不可能匹配的位置。
实现这一点的核心是构建一个叫做 next 数组（也叫失效函数或部分匹配表），记录模式串每个位置前最长的相等前缀和后缀长度。
next 数组的构造
next[i] 表示模式串从 0 到 i 这一段中，最长的相等真前缀与真后缀的长度。
立即学习“C++免费学习笔记（深入）”；
例如模式串 "ABABC"：
- "A" → 0
- "AB" → 0
- "ABA" → 1 ("A")
- "ABAB" → 2 ("AB")
- "ABABC" → 0
构造过程类似 KMP 匹配，用两个指针 j 和 i，j 表示当前最长前缀的下一个位置，i 遍历模式串。
// 构建 next 数组
vector
KMP 主匹配过程
使用 next 数组，在主串中逐个比较字符。当发生失配时，模式串指针回退到 next[j-1] 的位置，而不是从头开始。
int kmpSearch(const string& text, const string& pattern) { if (pattern.empty()) return 0; vectorfor (int i = 0; i < n; ++i) {
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
return i - m + 1; // 找到匹配，返回起始下标
}
}
return -1; // 未找到}
完整可运行示例
#include <iostream> #include <vector> #include <string> using namespace std;vector
int kmpSearch(const string& text, const string& pattern) {
if (pattern.empty()) return 0;
vector
for (int i = 0; i < n; ++i) {
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;}
int main() { string text = "ABABDABACDABABCABC"; string pattern = "ABABC"; int pos = kmpSearch(text, pattern); if (pos != -1) { cout << "Pattern found at index " << pos << endl; } else { cout << "Pattern not found" << endl; } return 0; }
基本上就这些。理解 next 数组的含义和构造方式是掌握 KMP 的关键。代码不复杂但容易忽略细节，比如 while 循环中的回退逻辑。多调试几个例子有助于加深理解。
