从暴力到KMP：一道题彻底搞懂字符串匹配的前世今生

力扣 28. 找出字符串中第一个匹配项的下标是很多同学入门字符串匹配的第一道题。暴力解法 5 分钟写完但当你看到 KMP 的代码时却总觉得“每个字母都认识连起来就看不懂了”。今天我们不背模板而是从暴力为什么慢出发一步步推导出 KMP 的精髓 ——next 数组到底是什么、怎么算、怎么用。读完你会发现KMP 不过如此。一、先写个暴力感受一下痛点题目要求很简单在haystack中找needle第一次出现的下标找不到返回 -1。暴力思路更简单从haystack的每个位置起依次比较needle的每个字符。只要有一个不匹配就 break从下一个位置重新开始。var strStr function(haystack, needle) { let len1 haystack.length; let len2 needle.length; let flag true; for(let i 0; i len1; i) { let temp i; for(let j 0; j len2; j) { if(haystack[temp] ! needle[j]) { flag false; break; } temp; flag true; } if(flag) return i; } return -1; };复杂度分析最坏情况下haystack aaaaabneedle aaab每次匹配到最后一个字符才失败然后 i 只前进一位重新比较。时间复杂度O(n*m)当 n、m 达到 10⁴ 时最坏 10⁸ 次比较可能超时。痛点在哪暴力匹配失败后主串指针 i 回退模式串指针 j 也回到 0之前已经比较过的信息全部丢弃。就像你抄了一份很长的笔记抄到一半发现抄错了一个字于是撕掉整页从头抄 —— 太浪费了KMP 的核心思想就是匹配失败时主串不回溯模式串尽量少回溯。而“尽量少回溯”究竟是多少就由next 数组来告诉你。二、KMP 的直觉利用“已匹配”部分的信息我们用一个经典例子来感受haystack ABABABCneedle ABABC暴力匹配到第 5 个字符时失败ABABABC ABABC ↑ 这里 A vs C 不匹配此时前面已经匹配了ABAB。如果我们能让j回退到某个位置使得needle的前缀能和主串已匹配的后缀对齐而不是直接回退到 0就能省去大量比较。观察needle ABABC已匹配部分ABAB的最长相等前后缀是AB长度 2。所以我们把 j 回退到 2即指向第三个字符A主串 i 不动继续比较ABABABC ABABC ↑ 继续比较 A vs A你看j从 4 退到 2而不是 0主串 i 没有回退。这就是 KMP 的魔力。而next[j]的定义正是当模式串第 j 位匹配失败时j 应该回退到的位置或者说needle[0..j-1]的最长相等前后缀的长度。三、手撕 next 数组标准前缀函数是怎么算出来的next 数组的正式定义以 0 为起始下标next[i]表示needle[0..i]这个子串中最长相等真前后缀的长度真前后缀指不包含整个子串本身。比如needle ABABCi0, A无真前后缀 → next[0] 0i1, AB前缀 A后缀 B不等 → 0i2, ABA前缀 A 等于后缀 A长度 1 → 1i3, ABAB前缀 AB 等于后缀 AB长度 2 → 2i4, ABABC前缀 A,AB,ABA 与后缀 C,BC,ABC 无相等 → 0所以 next [0, 0, 1, 2, 0]。但我们在匹配过程中是当needle[j]和haystack[i]不匹配时令j next[j-1]。换句话说我们需要的是已匹配部分长度为 j的最长相等前后缀长度即next[j-1]。为了方便很多实现里把 next 数组的定义微调为next[i]表示needle[0..i-1]的前后缀长度即长度为 i 的前缀信息。但上述代码你提供的使用的是标准递推计算next[i]表示needle[0..i]的前后缀长度并在匹配失败时用j next[j-1]。这是完全等价的我们接下来就逐行解析这种写法。3.1 next 数组的递推计算双指针法const next new Array(len2).fill(0); for (let i 1, j 0; i len2; i) { while (j 0 needle[j] ! needle[i]) { j next[j - 1]; } if (needle[j] needle[i]) { j; next[i] j; } }这个循环在做什么我们有两个指针i表示当前要计算的 next 值的位置后缀末尾j表示当前已匹配的前缀长度也是前缀末尾的下一个位置。我们希望找到needle[0..i]的最长相等前后缀长度利用已知的next[0..i-1]来递推。具体过程以ABABC为例i1, j0needle[0]Avsneedle[1]B不等不进 ifnext[1]0保持 j0。i2, j0AvsA相等j → 1next[2]1。i3, j1needle[1]Bvsneedle[3]B相等j → 2next[3]2。i4, j2needle[2]Avsneedle[4]C不等进入 whilej0 且 A!Cj next[j-1] next[1] 0。跳出 while此时 j0needle[0]AvsC不等next[4]0。关键难点while 里的j next[j-1]是啥意思当当前字符不匹配时说明我们之前假设的“长度为 j 的前后缀相等”已经不成立了于是我们退而求其次寻找更短的相等前后缀。而next[j-1]正好是needle[0..j-1]这个前缀的最长相等前后缀长度用它来更新 j继续比较。这本质上是一个递归回退过程和主串匹配失败时的回退逻辑如出一辙。说白了求 next 数组的过程就是在模式串自己身上“自匹配”用的正是 KMP 匹配的同一套逻辑。四、匹配过程next 数组的实战应用有了 next匹配就变得非常简单for (let i 0, j 0; i len1; i) { while (j 0 haystack[i] ! needle[j]) { j next[j - 1]; } if (haystack[i] needle[j]) { j; } if (j len2) { return i - len2 1; } } return -1;这里i是主串指针永远只向前移动j是模式串指针失败时通过 next 回退。匹配成功j len2时返回起始下标i - len2 1。还是那个例子haystackABABABC,needleABABC,next[0,0,1,2,0]。i0, j0: AA → j1i1, j1: BB → j2i2, j2: AA → j3i3, j3: BB → j4i4, j4: A vs C 不等 → while: jnext[3]2此时 j2haystack[4]Avsneedle[2]A相等 → j3i5, j3:haystack[5]Bvsneedle[3]B→ j4i6, j4:haystack[6]Cvsneedle[4]C→ j5 → 匹配成功返回 6-512完全正确且主串 i 从未回退。五、完整代码与复杂度var strStr function(haystack, needle) { const n haystack.length, m needle.length; if (m 0) return 0; // 防御性处理虽然题目保证非空 // 1. 求 next 数组 const next new Array(m).fill(0); for (let i 1, j 0; i m; i) { while (j 0 needle[j] ! needle[i]) { j next[j - 1]; } if (needle[j] needle[i]) { j; next[i] j; } } // 2. 匹配 for (let i 0, j 0; i n; i) { while (j 0 haystack[i] ! needle[j]) { j next[j - 1]; } if (haystack[i] needle[j]) { j; } if (j m) { return i - m 1; } } return -1; };时间复杂度O(n m)两个循环中 while 的总执行次数是 O(m) 和 O(n) 级别的因为 j 每次回退后都会再前进但总回退次数不超过前进次数。空间复杂度O(m) 用于存储 next 数组。六、KMP 到底解决了什么问题—— 几个金句帮你记暴力匹配是“知错就改改完从头再来”KMP 是“知错就改改完继续前进”。主指针永不回溯是 KMP 效率的根本保证。next 数组不是算法黑盒而是“模式串自己的失败经验记录表”。它告诉我们当模式串走到某个位置走不通时可以退回到哪个“安全位置”继续走而不必回到起点。学 KMP 不要死记代码要记住两个“匹配”先让模式串和自己匹配求 next再让主串和模式串匹配用 next七、一个容易踩的坑next 数组的“长度”与“下标”对应关系很多初学者会把 next 数组搞混这里用一个对比帮你理清实现方式next[i] 含义匹配失败时回退标准前缀函数本文needle[0..i]的最长相等前后缀长度j next[j-1]偏移版常见于教材next[i]表示当needle[i]失配时j 跳到的位置即next[i] 标准next[i-1]j next[j]两种写法等价但一定要保持一致。本文的写法更直观因为next[i]直接对应子串本身的属性理解起来更自然。八、小结与拓展KMP 算法虽然经典但并不是银弹。当模式串较短或字符集较大时暴力往往更快因为常数小。但在大量文本匹配、搜索引擎、编译原理的词法分析等场景KMP 的思想前缀函数是不可或缺的基础。真正理解 KMP 之后你会发现它不只是解决一道题而是教会你一种“利用历史信息指导未来决策”的思维方式。这种思维在动态规划、缓存设计、甚至是写业务代码时都同样受用。