从暴力匹配到 KMP，我是怎么把它啃下来的

最近在学习数据结构中的 KMP 算法，说实话，遇到了不少障碍。字符串匹配这部分内容，我以为是个没啥难度的“套路题”，结果越学越混乱，尤其是那个什么 next 数组、PM 值、跳转逻辑，整得我一度差点放弃。后来一点点摸清了它的来龙去脉，也想写一篇博客分享下我的理解过程，也许能帮到也卡在这儿的你。

这个算法到底有啥用？

KMP 算法解决的问题很实在——在主串中查找一个模式串的位置。比如你用 Ctrl+F 查找关键词、搜索引擎在网页中匹配内容、DNA序列分析等，底层其实都离不开字符串匹配。

最朴素的方法就是暴力匹配，从主串每一个字符开始尝试跟模式串匹配，一旦发现不匹配，就从下一个字符再来一次。但问题在于：太慢了！最坏情况下主串长度是 n，模式串长度是 m，时间复杂度就是 O(n*m)。

这时候，KMP 这个“能记住你已经匹配过的信息”的算法就登场了。

看似简单，其实浪费了太多重复操作。举个例子：

主串：a a b a a b c a
模式：a a b c

前面三个字符 aab 都匹配了，但在第4个字符发现 a ≠ c 后，暴力法会怎么做？

👉 从主串的第二个字符 a 再试一次，之前匹配的信息全白干了。

这太不聪明了，KMP 就是在这时候帮我们“记住之前成功匹配的部分”，避免无意义的重复。

我一开始特别纠结 next 数组是怎么来的，什么 PM 值，next[j] = PM[j-1]，网上一堆说法，绕晕了。

后来我明白了，本质上，PM[j] 表示的是模式串前 j 个字符中，前缀 = 后缀的最大长度。

比如：

模式串：a a b a a b
          |     |
        前缀   后缀
最长的前后缀相等：aab，长度为 3

然后用 PM 值推 next 数组，是为了方便跳转：

next[j] = PM[j - 1];

这个 next[j] 告诉你：如果模式串第 j 个字符匹配失败，那就跳到 next[j] 位置继续匹配。

注意：这个 j 是“当前准备要匹配的字符位置”。匹配失败时，并不是让主串动，而是让模式串向右滑动（也就是 j 更新成 next[j]）！

一开始我不理解“为什么主串不动”，其实换个角度就通了：主串指针一直在往前走，只是模式串遇到失配就往右跳，所以你会感觉“好像在滑动整个模式串”，其实只是 j 在变而已。

来张配图：

主串：     a  a  b  a  a  b  c
模式串初始：a  a  b  c
          ↑  ↑  ↑  ↑
          i        j

匹配到 c 时失败，next[3]=0 → j=0
然后继续从主串的 c 与 模式串第0位重新开始。

KMP 就靠这个 next 数组，在失败时快速定位下一个可尝试匹配的位置，不必从头来过。

经典 next 数组会在某些重复字符下，导致无谓的尝试（比如 aaaaaa）。于是有了优化版 nextval 数组。

核心思想是：

如果 next[j] 位置上的字符和当前字符一样，那继续跳，直到跳到一个不一样的位置。

代码写法上通常变成这样：

if (pattern[next[j]] == pattern[j])
    nextval[j] = nextval[next[j]];
else
    nextval[j] = next[j];

不过我个人建议：先搞懂 next 数组，优化版属于锦上添花，不急。

KMP 的精髓在于：

用 next 数组记录前缀信息，当匹配失败时，直接跳过已经比较过的一部分字符，让时间复杂度降低到 O(n+m)。

主串 i 不动，模式串 j 靠 next 数组跳转，这样我们不用回退主串的位置，就像模式串在主串上“智能滑动”。

如果你也在学习 KMP，欢迎留言交流你卡住的点，或你的理解角度～

🧠 最后提醒一句：KMP 看起来难，是因为你试图一下子理解它所有的逻辑。分步骤来，先理解 “为什么跳”，再理解 “怎么跳”，最后再去优化，那就稳了。