KMP算法学习笔记

kmp即字符串快速查找算法。

传统的查找算法会进行多次回溯，造成资源浪费时间复杂度O(n*m)。kmp通过预处理模式串、构造 next 数组，利用已匹配的前缀/后缀信息，在失配时只移动模式串而不回溯主串指针复杂度O(n+m)，解决了这一点。

---

Step0 前置概念：最长相等前后缀

想要理解 Next 数组，必须先搞懂 前缀、后缀、最长相等前后缀 三个概念（针对模式串）：

• 前缀：包含首字符、不包含最后一个字符的所有连续子串
• 后缀：包含最后一个字符、不包含首字符的所有连续子串
• 最长相等前后缀：同一子串中，长度最大、且完全相等的前缀和后缀，其长度就是Next数组的核心取值

举例：模式串 ababc，对于前4位子串 abab：

前缀集合：a、ab、aba；后缀集合：b、ab、bab；最长相等前后缀为 ab，长度为2。

这个长度的意义至关重要：字符失配时，模式串可以直接跳转到该长度的下一个位置继续匹配，无需从头开始。

Step1：预处理模式串

Next 数组是 KMP 算法的灵魂，数组中 next[i] 的含义为：模式串前 i 个字符组成的子串，最长相等前后缀的长度。

数组初始化规则

1. 模式串第一个字符无前后缀，固定 next[0] = 0；

2. 采用双指针遍历方式构建数组：定义指针 i 指向当前遍历位置（初始为1），指针 j 记录当前最长相等前后缀长度（初始为0）；

匹配逻辑

1. 字符匹配成功：若 pattern[i] == pattern[j]，说明前后缀匹配长度+1，j++，赋值 next[i] = j，同时 i++，继续向后遍历；
2. 字符匹配失败：若 pattern[i] != pattern[j]，且 j != 0，则 j = next[j-1]（回溯到上一个可匹配的最长前缀位置），重新比对；若 j == 0，说明无匹配前后缀，直接赋值 next[i] = 0，i++。‘

Step2：匹配

完成模式串预处理、得到Next数组后，即可开始主串与模式串的匹配工作，全程遵循主串指针不回溯原则：

1. 定义双指针：i 遍历主串（初始0），j 遍历模式串（初始0）；
2. 字符匹配成功（text[i] == pattern[j]）：i、j 同时后移，继续比对下一位；
3. 字符匹配失败（text[i] != pattern[j]）：
   1. 若 j != 0：利用Next数组回溯，j = next[j-1]，复用已匹配前缀，无需重置到0；
   2. 若 j == 0：无可用前缀，主串指针 i++，从下一位重新匹配；
4. 终止条件：j 遍历完整个模式串，说明匹配成功，返回匹配起始位置；i 遍历完主串仍未匹配成功，说明无匹配结果。

---

※Final：我认为的难点

构建 Next 数组时，pattern[i] != pattern[j]，执行 j = next[j-1]

构建 next 数组本身也是一次 KMP 匹配，模式串自己和自己匹配。

• i：当前正在计算 next 值的位置（不断往前走，不会回退）
• j：当前最长相等前后缀的长度，同时也是待比较前缀的位置

举个例子：模式串 a a B a a a 初始：next[0]=0，i=1,j=0

1. pattern[i]==pattern[j] → j++，next[i]=j，i++
2. 如果不等：不能直接 j=0！ 因为 pattern[0...j-1] 这段是匹配成功的，它内部依然存在更短的相等前后缀。 所以要回退：j = next[j-1]，拿更短的前缀，再次和 pattern[i] 比较。直到 j=0，如果还不相等，next [i]=0，i++。

总之，无论是构建 next 数组，还是正式字符串匹配，当字符失配时 j = next[j-1] 指的是： 当前已经匹配成功的子串，仍然存在更短的相等前后缀。我们回退 j，去复用这个更短的前缀，而不是直接放弃全部已匹配内容。