KMP这个算法大概是很多人在代码随想录刷题路上遇到的第一道硬骨头。别看前面的链表、哈希表、双指针都能顺风顺水写过去一到第九天的KMP很多人直接卡了一周。我自己带过不少人刷题几乎每个人都会在next数组这一步懵掉视频看了一遍觉得懂了关上屏幕自己写不是死循环就是越界要不就是匹配结果不对。最折磨人的是网上一搜KMP各种版本的next数组定义还不一样有的从0开始存有的整体右移有的第一位是-1代码长得完全不一样越看越乱。今天这篇就想把KMP这件事彻底讲明白。我不会只丢给你一段代码让你背而是把next数组为什么这么算、匹配的时候为什么要这么跳、不同版本的代码差异到底在哪全部掰开揉碎讲清楚。不管你是准备面试、应付考试还是单纯想把字符串匹配搞明白这篇都适用。读完你至少能做到手推任意模式串的next数组手写匹配代码不卡壳并且能跟面试官把“为什么复杂度是O(nm)”这件事说清楚。1. KMP到底在解决什么问题1.1 先看朴素的字符串匹配有多亏假设我们要在主串 s aabaabaaf 里找模式串 p aabaaf最简单粗暴的方式就是从左往右一位一位试先用主串的第0位开始和模式串对齐逐位比较如果中间某一位失配了就把整个模式串往右移一格再从模式串第0位开始重新比较。这个过程用人话说就是主串的指针 i 一会儿往前走一会儿往回退模式串指针 j 动不动就归零。最坏情况下主串长度为 n模式串长度为 m每移动一次主串指针就要比较 m 次总复杂度是 O(n×m)。当模式串很长、且重复字符很多的时候这个乘法关系会非常吓人。我见过很多人在暴力匹配。“aabaaf”这种例子里还能忍如果模式串是aaaaab主串是aaaaaaaaab暴力匹配几乎每个位置都要完整比到最后一个字符才失配那个效率是真的没法看。1.2 KMP的核心思想让主串指针少回头KMP算法的核心突破点在于主串的指针 i 不回头一直往前走失配时只让模式串的指针 j 往回跳到一个合适的位置。“合适”这两个字是关键它意味着我们要提前预处理模式串记住一些信息让下次比较能够直接从某个位置开始而不是每次都要回到模式串的第0位重来。这个预处理结果就是next数组。你可以把next数组理解成模式串自己给自己画的“回退地图”当第 j 位失配时不用从头开始而是跳到地图上指定的位置继续比。为什么能这样因为主串中已经比较过的那些字符里有一部分其实已经和模式串的某个前缀匹配上了这部分信息完全可以复用不需要白白浪费掉。2. next数组的本质最长相等前后缀2.1 什么是前缀和后缀在讲next数组之前必须先搞懂两个概念。一个字符串的前缀是包含串首字符、但不包含串尾字符的任意子串后缀是包含串尾字符、但不包含串首字符的任意子串。以模式串 aabaa 为例。它的前缀有a、aa、aab、aaba注意 aabaa 本身不算自己的前缀。它的后缀有a、aa、baa、abaa同样 aabaa 本身不算。这前后两组里长度相等又内容相同的就是相等前后缀。比如 a 是aa 也是长度更长的就没有了。为什么要关心前缀后缀因为字符串匹配失败的瞬间我们已经知道主串当前位置之前的若干字符完全等于模式串的某段前缀。这一段里前缀和后缀的重叠情况直接决定了模式串能往右滑多远。你可以把它想成两组积木左边一摞是前缀右边一摞是后缀只有当它们高度一样、花色也一样的时候才能稳稳地叠在一起复用。2.2 最长相等前后缀怎么算对于模式串的每一个位置 i我们关心的是从第0位到第 i 位这个子串中最长相等前后缀的长度是多少。这个长度就是 next[i] 的值也叫做这个子串的部分匹配表Partial Match Table数值。拿 aabaaf 来举例从第0位开始依次看子串 a只有1个字符前缀和后缀都是空集最长相等前后缀长度为0。子串 aa前缀有 a后缀有 a最长相等前后缀长度为1。子串 aab前缀有 a、aa后缀有 b、ab没有相等的长度为0。子串 aaba前缀 a、aa、aab后缀 a、ba、aba只有 a 相等长度为1。子串 aabaa前缀 a、aa、aab、aaba后缀 a、aa、baa、abaaa 和 aa 相等最长的是 aa长度为2。子串 aabaaf前缀有一堆后缀末尾是 f没有相等的情况长度为0。所以模式串 aabaaf 每个位置对应的最长相等前后缀长度就是0、1、0、1、2、0。这个数组就是我们说的next数组写成 [0, 1, 0, 1, 2, 0]。2.3 next数组的不同版本新手最大的坑这里必须专门讲一下版本问题因为网上资料实在太乱了。同一个模式串在不同教材里可能给出完全不同的next数组但背后的逻辑其实是一回事只是存法不同。版本aabaaf 的 next 数组失配时回退写法说明前缀表原样存储代码随想录常用[0, 1, 0, 1, 2, 0]j next[j - 1]数组长度和模式串相同下标0固定为0右移一位首位置-1[-1, 0, 1, 0, 1, 2]j next[j]注意处理-1失配位直接用当前下标查表经典教材右移再减1[-1, 0, 1, 0, 1, 2, 0]j next[j]next[0] 是哨兵-1严格来说值等于前一位的前缀表值看到这个表格你可能更晕了但我建议的做法是刷题和面试就死磕第一个版本也就是代码随想录推荐的版本。它最直观下标和模式串一一对应不容易在回退的时候把下标搞错。至于其他版本优先级很低等你能熟练写出第一个版本之后再去看就很容易理解它们是怎么变出来的了。3. 手把手推一遍next数组3.1 初始化与整体思路next数组的构建过程本质上是模式串自己和自己做KMP匹配。逻辑上我们用两个指针j 表示已经匹配成功的前缀长度i 表示当前正在处理的后缀末尾位置。初始状态是 i 1j 0next[0] 0 是固定的因为单字符没有相等前后缀。然后 i 从1开始一直遍历到模式串末尾每一步做的事情可以概括成三段不相等就回退相等就前进最后记录 next[i]。为了让你看得清楚我写一个Python风格的伪代码def build_next(p): n len(p) next [0] * n j 0 for i in range(1, n): while j 0 and p[i] ! p[j]: j next[j - 1] if p[i] p[j]: j 1 next[i] j return next这个代码只有十几行但里面的 while 回退是绝大多数人理解不了的坎。我接下来就用 aabaaf 一步一步走给你看。3.2 以 aabaaf 为例的逐步推演我用一个表格把每次循环的现场记录整理出来ip[i]当前j比较情况执行动作最终jnext[i]0a0初始化固定next[0]0001a0p[1]p[0]j加1112b1p[2]!p[1]回退jnext[0]0p[2]仍不等于p[0]j保持0003a0p[3]p[0]j加1114a1p[4]p[1]j加1225f2p[5]!p[2]回退jnext[1]1p[5]!p[1]再回退jnext[0]0p[5]!p[0]00这个推演过程建议你拿笔在纸上自己画一遍尤其是 i5 那一步是从 j2 一路回退到 j0中间经历了两次回退。很多人的困惑就在这为什么 p[5] 和 p[2] 不相等之后要去看 next[1]而不是直接把 j 清零因为 next[1]1它表示的是子串 aa 的最长相等前后缀长度是1。也就是说虽然当前尝试扩展的前缀后缀接不上了但更短的前后缀可能还有希望所以要先跳到那个短一截的位置再试试而不是彻底放弃。3.3 回退代码里的jnext[j-1]到底在干什么这里必须把 next[j-1] 的意思讲透。当 p[i] ! p[j] 时说明以 i 结尾的后缀没法直接接上长度为 j 的前缀。但我们并不想直接清零因为 p[0..j-1] 这一段已经匹配成功了这段内部可能还有重叠的前后缀。next[j-1] 表示的是子串 p[0..j-1] 的最长相等前后缀长度。我们把这个长度作为新的 j就相当于把“已经匹配好的部分”缩到最短的重复段然后再拿 p[i] 去和新的 p[j] 比较。如果还是不相等就继续用同样的逻辑回退直到 j 变成0或者遇到相等的字符为止。这里常见的误区是把回退写成 j next[i] 或者 j next[j]版本不同写法确实不同但在当前这个前缀表原样存储的版本里回退对象必须是 next[j-1]不是 next[j]也不是 next[i]。我见过好多人改代码把这里写错结果就是要么数组越界要么结果永远差一位。为了验证你确实懂了建议再手推一个连续回退的例子比如模式串 aabaaa 的next数组。它的推演过程中i5 时 p[5]a 先和 p[2]b 比不相等回退到 j1p[5]a 和 p[1]a 相等这时候 j2next[5]2。这个例子的价值在于它展示了回退之后可能立刻就有新的字符能匹配上而不是回退到底才重新匹配。很多教程只讲 aabaaf会让你误以为回退都是回退到0其实不是。4. 真正跑一遍KMP匹配4.1 匹配主流程代码next数组构建好了匹配就变得非常简单。主串指针 i 从头走到尾模式串指针 j 负责跟着走失配时根据next数组回退。完整代码如下def kmp_search(s, p): next build_next(p) j 0 for i in range(len(s)): while j 0 and s[i] ! p[j]: j next[j - 1] if s[i] p[j]: j 1 if j len(p): return i - j 1 # 找到了返回起始下标 return -1 # 没找到这段代码和构建next的代码结构惊人地相似因为KMP本身就是“一个算法用两遍”构建next是模式串匹配自己查找是主串匹配模式串。理解了这个对称性你在面试时就很容易少写很多代码。4.2 用例子验证匹配过程继续用主串 s aabaabaaf、模式串 p aabaaf 跑一遍。上面的推演已经得到 next [0, 1, 0, 1, 2, 0]匹配过程的现场如下主串下标i主串字符当前模式串下标j比较结果动作0a0相等j11a1相等j22b2相等j33a3相等j44a4相等j55b5失配jnext[4]2回退后重新比较5b2bb相等j36a3相等j47a4相等j58f5相等j6jlen(p)匹配成功匹配成功的位置 i8返回的起始下标是 i - j 1 8 - 6 1 3也就是主串从下标3开始是 aabaaf。你可以自己数一下s[3..8] 恰好就是 aabaaf完全正确。这里有个很直观的对比同样这个例子暴力匹配需要比较15次字符而KMP只比较了10次省下的次数全部来自失配后的“有脑回退”而不是“无脑从头再来”。4.3 为什么时间复杂度是O(nm)很多人背结论说KMP是O(nm)但不知道这个结论为什么成立。道理其实不复杂主串指针 i 在整个匹配过程中单调递增最多走 n 步模式串指针 j 每次增大都发生在匹配成功时最多增大 m 次。而 while 循环里的回退操作每次都会让 j 至少减少1但 j 的总增大量不超过 m所以回退总次数也不会超过 m。整体加起来主串遍历 n 次模式串相关操作 m 次左右总复杂度就是 O(nm)。也就是说KMP把原本的乘法复杂度变成了加法复杂度这是质的提升。字符串匹配在大文本检索、编辑器查找、日志分析里是个高频操作数据量一大这个提升就非常明显了。5. 我踩过的坑和常见问题汇总5.1 next数组构建中的死循环与越界我见过最多的错误是初学者把 while 循环的条件写成了 while p[i] ! p[j]漏掉了 j 0 这个前置条件。这样当 j 已经回退到0但 p[i] 仍然不等于 p[0] 时代码会继续执行 j next[j - 1]也就是 j next[-1]直接数组越界程序崩溃。这个 j 0 相当于一道路障拦住你回退到负数的情况。另外还有个细节如果 p[i] ! p[0]此时 while 不会进入if 判断也不成立j 保持0next[i] 赋值为0。也就是说next[i] 等于0表示以 i 结尾的这个子串没有任何相等前后缀。这个逻辑很多第一次写的人在 if 之后忘了赋值导致 next 数组后面全是默认值匹配结果自然不对。5.2 不同next数组版本的混淆问题这是KMP最大的坑。你背了一个版本的写法结果在网上搜代码发现别人的写法长这样void getNext(string p, int next[]) { int j 0, k -1; next[0] -1; while (j p.length() - 1) { if (k -1 || p[j] p[k]) { j; k; next[j] k; } else { k next[k]; } } }不要说新手有几年经验的工程师看到这代码也得愣一下。这是经典教材里把k初始化为-1的写法和代码随想录的写法完全两套。我的建议很明确认准一种版本写熟它面试时就按那个版本写。如果面试官问“能说下另一种版本吗”你只需要说“我知道next数组有右移和减1的变体核心逻辑是一样的只是存储方式不同”然后对比一下就行不用真去默写第三种。5.3 匹配成功后如何找下一个匹配位置如果面试题要求找出所有匹配位置而不是第一个匹配成功之后不能直接 return。正确的做法是在 j len(p) 时记录当前起始下标然后执行 j next[j - 1]继续往后走。这一步的原理是匹配成功的一段里仍然可能存在重叠的前后缀所以通过回退可以无缝衔接下一次匹配主串指针完全不需要回退。举个例子模式串 aa主串 aaaa最暴力的匹配能找到3个位置下标0、1、2。用KMP找全部位置时第一次匹配成功 j2记录下标0然后 jnext[1]1继续遍历在主串下标2时再次匹配成功记录下标1如此往复。这个技巧在很多字符串题目里直接能用比如统计一段文本里某个单词出现的次数。5.4 面试高频追问nextval是什么如果面试官想加深难度大概率会问“next数组还有没有优化的空间”这里引入nextval的概念。nextval的核心优化点是如果回退后的那个字符和失配时的字符一样那这次回退其实没有意义因为下一次比较肯定还是会失配。比如模式串 aaaaab 的 next 数组是 [0,1,2,3,4,0]在某个 a 失配时回退到更早的一个 a比较时还是会失配白白浪费一次比较。nextval只是把这种情况的next值继续往前传递跳过这些无效比较。理解这个优化的关键还是在于先把基础next数组写熟否则容易把自己的思路绕进去。5.5 一个实用性建议先背场景再背代码最后说一个我自己的经验。KMP这个算法除非你天天写字符串匹配否则搁置三个月很容易忘。我建议你不要只背代码而是记住两个关键场景一个是主串指针 i 永不回头一个是失配时查 next[j-1]。只要这两个画面在脑子里立住了代码是可以现场推出来的。我自己后来每次写KMP都是从“自己匹配自己”这个场景开始现场构建next反而比死记硬背更不容易出错。另外刷题时如果只是想通过代码随想录第九天的内容不用过分追求一次写对。我建议先在纸上把 next 数组手推三遍再用代码验证然后再跑匹配流程。这个过程看似慢其实比反复看视频高效得多。KMP值得你花这一两个小时因为字符串匹配的思想在后续很多题目里都会用到比如重复子串判断、回文串预处理都藏着KMP的影子。