C++KMP算法
KMP 算法详解：从暴力匹配到高效字符串查找（附 C++ 代码）
作者：poplar
标签：C++ / 字符串 / KMP / 算法 / 面试
在 LeetCode 第 28 题 「实现 strStr()」 中，要求我们在一个字符串（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 数组
voidgetNext(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 数组匹配
intstrStr(string haystack
