KMP 算法详解：从暴力匹配到高效字符串查找
在经典字符串查找问题中，要求在一个字符串（haystack）中查找另一个字符串（needle）首次出现的位置。如果用暴力法，时间复杂度是 O(n×m)，但在实际工程和面试中，我们更希望用 O(n + m) 的高效算法 —— 这就是 KMP（Knuth-Morris-Pratt）算法。
本文将带你从零彻底搞懂 KMP，包括：
- 为什么需要 KMP？
- 什么是前缀表（Prefix Table）？
- 如何构建 next 数组？
- 如何用 next 数组进行匹配？
- 两种主流实现方式（前缀表减一 vs 不减一）
一、为什么需要 KMP？—— 暴力匹配的痛点
假设：
haystack = "aabaabaafa"needle = "aabaaf"
暴力匹配过程如下：
- 从
haystack[0]开始匹配，前 5 个字符都匹配成功（a a b a a） - 到第 6 个字符时，
haystack[5] = 'b'，needle[5] = 'f'→ 不匹配 - 暴力法会回退到
haystack[1]重新开始匹配
但注意：前面已经匹配了 'aabaa'，其中包含重复信息（如前缀 'aa' 和后缀 'aa' 相同）。 KMP 的核心思想就是：利用已匹配部分的信息，避免从头开始匹配！
二、KMP 的灵魂：前缀表（Prefix Table）
✅ 什么是前缀？什么是后缀？
对字符串 "aabaaf"：
- 前缀：不包含最后一个字符的所有以第一个字符开头的连续子串
→
"a","aa","aab","aaba","aabaa" - 后缀：不包含第一个字符的所有以最后一个字符结尾的连续子串
→
"f","af","aaf","baaf","abaaf"
⚠️ 注意：前缀 ≠ 子串，必须从头开始；后缀必须到尾结束。
✅ 什么是最长相等前后缀？
对每个位置 i，计算 s[0..i] 的最长相等前后缀长度。
例如：
| 子串 | 最长相等前后缀 | 长度 |
|---|---|---|
"a" | 无 | 0 |
"aa" | "a" == "a" | 1 |
"aab" | 无 | 0 |
"aaba" | "a" == "a" | 1 |
"aabaa" | "aa" == "aa" | 2 |
"aabaaf" | 无 | 0 |
所以前缀表为：[0, 1, 0, 1, 2, 0]
🎯 前缀表的作用：当匹配失败时，告诉我们模式串应该跳到哪个位置继续匹配。
三、next 数组：前缀表的两种实现方式
在 KMP 中，通常用 next 数组来存储前缀表。但有两种主流实现：
方式 1️⃣：前缀表不减一（直接使用）
next[i] = s[0..i] 的最长相等前后缀长度- 示例：
"aabaaf"→next = [0, 1, 0, 1, 2, 0]
方式 2️⃣：前缀表统一减一（右移一位）
next[0] = -1，其余next[i] = 原前缀表 [i-1]- 示例：
"aabaaf"→next = [-1, 0, -1, 0, 1, -1]
💡 两种方式都能正确工作，只是匹配时的指针逻辑不同。 本文将分别讲解两种实现！
四、方式一：前缀表不减一（推荐初学者）
步骤 1：构建 next 数组
void getNext(int* next, const string& s) {
int j = 0; // j 表示前缀末尾
next[0] = 0;
for (int i = 1; i < s.size(); i++) {
// 前后缀不相同，j 回退
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
// 前后缀相同，j 向前移动
if (s[i] == s[j]) {
j++;
}
next[i] = j; // 记录当前最长相等前后缀长度
}
}
步骤 2：使用 next 数组匹配
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
vector<int> next(needle.size());
getNext(next.data(), needle);
int j = 0;
for (int i = 0; i < haystack.size(); i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = next[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == needle.size()) {
return i - j + 1;
}
}
return -1;
}
