字符串匹配是写程序时绕不开的活从文本编辑器里的查找替换到日志系统里过滤关键词再到生物信息里比对DNA片段本质上都在做同一件事给定一个主串和一个模式串找出模式串在主串中的位置。KMP算法就是解决这个问题的经典方案全称是Knuth-Morris-Pratt算法由三位计算机科学家在1977年联合提出。很多人第一次接触它是在数据结构课上但真正把它用明白、能手写出来往往要等到实际写代码踩过几次坑之后。这篇内容围绕KMP算法的核心——next数组展开重点手算一个具体例子模式串pabacaba的next数组到底怎么求以及求出来之后如何驱动整个匹配过程。我尽量用实际写代码的视角来讲不堆公式把每一步为什么这么做讲清楚。适合正在学数据结构的同学、准备算法面试的开发者以及那些学过KMP但总感觉“懂了又没完全懂”的人。1. 暴力匹配的问题与KMP的核心思想1.1 暴力匹配为什么慢先看最直观的暴力匹配思路。假设主串s长度为n模式串p长度为m做法是让模式串从主串的每个位置开始对齐然后逐个字符比较全部匹配就返回位置中途失配就整体右移一位重新比较。def brute_force(s, p): n, m len(s), len(p) for i in range(n - m 1): j 0 while j m and s[i j] p[j]: j 1 if j m: return i return -1这个代码很好理解但性能隐患很大。考虑一个极端场景主串是aaaaaaaaaaaaaaaaaaaaaaaaaab模式串是aaaaab每次匹配都要比较到模式串最后一个字符才发现b不匹配然后主串指针只前进一位又来一遍。整体时间复杂度是O(n*m)主串和模式串一长程序就肉眼可见地卡顿。暴力匹配浪费在哪里浪费在那些“已经比较过的、匹配成功的信息”上。主串第i位开始匹配时前面已经确认s[i..ij-1]等于p[0..j-1]这部分信息是花了时间比较出来的但当p[j]失配时暴力做法直接放弃这一整段信息把模式串挪一位从头比。实际上我们已经知道主串这一段长什么样了完全可以用这个信息来决定模式串跳到哪个位置更合理。1.2 KMP的一句话核心KMP算法的核心思想非常朴素当模式串在第j个位置失配时不要简单地右移一位而是根据模式串自身的结构把模式串指针j回退到一个合适的位置主串指针i不回退。这样主串从头到尾只需要扫描一遍时间复杂度从O(n*m)降到了O(nm)。那“合适的位置”怎么确定这就要看模式串失配位置之前的子串它的前缀和后缀有多少是重合的。举个例子模式串abacaba在最后一个a失配时前面abacab已经匹配成功了如果abacab有一个较长的前缀和后缀相等那我们就能把这个前缀挪到刚才后缀的位置上因为这些字符已经被主串验证过了不需要重新比较。这个“失配时回退到哪里”的信息就是提前预处理出来的next数组。理解了这一点KMP就不再是死记硬背的代码模板而是一个逻辑上非常顺其自然的优化方案。2. next数组的定义与手算以pabacaba为例2.1 next数组想表达什么next数组的经典定义是对于模式串pnext[i]表示当p[i]与主串字符失配时模式串指针i应该回退到的位置。换句话说回退位置取决于p[0..i-1]这段已经匹配成功的子串中最长相等前后缀的长度。这里有两个概念必须先拆清楚“前缀”和“后缀”。前缀是指从子串第一个字符开始、但不包含最后一个字符的任意连续子串后缀是指以子串最后一个字符结尾、但不包含第一个字符的任意连续子串。比如子串abac它的前缀有a、ab、aba后缀有c、ac、bac前后缀相等的只有长度0也就是说没有任何相同的前后缀。如果子串abab前缀有a、ab、aba后缀有b、ab、bab相等的有a和ab最长相等前后缀长度是2。这个“最长相等前后缀”就是next数组的核心素材它告诉我们当这一段匹配成功后遇到失配模式串可以直接把前缀挪到后缀的位置上不用回到开头。2.2 手算pabacaba的next数组现在手算题目里这个具体的模式串。p abacaba下标从0开始位置分别是0a1b2a3c4a5b6a。我按照“next[i] p[0..i-1]的最长相等前后缀长度”这个定义来算这也是最常见的数据结构教材定义。逐个位置推一遍next[0]p[0]之前没有字符是一个特殊位置约定为-1代表模式串已经无法再回退需要主串指针前移。next[1]看p[0..0]a只有一个字符没有真正的前缀和后缀最长相等前后缀长度为0。next[2]看p[0..1]ab前缀有a后缀有b不相等长度为0。next[3]看p[0..2]aba前缀有a、ab后缀有a、ba相等的只有a长度为1。next[4]看p[0..3]abac前缀a、ab、aba后缀c、ac、bac没有相等的长度为0。next[5]看p[0..4]abaca前缀a、ab、aba、abac后缀a、ca、aca、baca相等的只有a长度为1。next[6]看p[0..5]abacab前缀a、ab、aba、abac、abaca后缀b、ab、cab、acab、bacab相等的最长的是ab长度为2。整理成表格ip[i]p[0..i-1]最长相等前后缀长度next[i]0a空--11ba002aab003caba114aabac005babaca116aabacab22所以pabacaba的next数组是[-1, 0, 0, 1, 0, 1, 2]。这是按“失配时模式串指针回退到next[i]”的定义来的也是最常见的写法。2.3 另一种定义与换算这里必须多说一句因为next数组在不同教材、不同文章里定义差异很大特别容易把人搞晕。我见过至少三种第一种就是我上面用的next[i]表示p[0..i-1]的最长相等前后缀长度next[0]-1失配时i回退到next[i]。C语言风格的教材和大部分考研资料用这种。第二种next[i]表示p[0..i]的最长相等前后缀长度next[0]0失配时i回退到next[i-1]。这种写法的代码更统一但要特别小心边界。用这种定义算pabacaba结果是[0, 0, 1, 0, 1, 2, 3]和第一种定义相比整体错了一位。第三种从下标1开始存储next[1]0next[j]表示p[0..j-2]的最长相等前后缀长度再加1。这是严蔚敏版数据结构教材的写法面试时偶尔会遇到。我的建议是自己写代码时认准一种定义把对应的匹配逻辑写对就行读别人的文章时先看它的初始化和失配回退代码反推它用的是哪种定义不要拿A定义的数组去套B定义的匹配逻辑。否则结果对不上还以为是自己算错了。3. 递推求解next数组原理与代码3.1 为什么可以递推求next数组如果每个位置都从头数一遍前缀后缀那复杂度又回到O(n*m)了得不偿失。KMP的精髓在于next数组本身也可以递推得到。假设我们已经知道next[0..i-1]的值现在要求next[i]。注意next[i]描述的是p[0..i-1]的最长相等前后缀长度它其实和next[i-1]描述的对象有关系。如果p[i-1] p[next[i-1]]那说明在上一段最长相等前后缀的基础上后面又续上了一个字符所以next[i] next[i-1] 1。如果字符不相等呢那就不能直接续上了需要退一步找更短的相等前后缀。这个“退一步”不是随便退而是退到next[next[i-1]]的位置因为这个位置记录了更短的前缀信息。这个过程可能会循环几次直到找到相等的字符或者退到-1或0取决于定义为止。这个递归式的回退逻辑是整个KMP算法里最绕的地方。我当初学的时候也是在这个地方卡了很久。用一句话总结next数组的求解本质上是在用KMP的思想自己匹配自己模式串既是主串又是模式串。3.2 完整代码我用Python写一版完整的next数组求解采用2.2节的定义失配时i回退到next[i]def build_next(p): m len(p) nxt [-1] * m i, j 0, -1 while i m - 1: if j -1 or p[i] p[j]: i 1 j 1 nxt[i] j else: j nxt[j] return nxt这段代码很短但每一行都有讲究。i是当前要计算next的位置j记录的是上一个位置的next值也就是当前已匹配的前缀长度。当p[i] p[j]时说明最长相等前后缀可以延长一位于是i和j各前进一位nxt[i]就是新的j。当字符不相等时j回退到nxt[j]继续尝试更短的前缀。如果j回退到-1说明没有任何相等前后缀nxt[i]直接是0。这个写法虽然有-1这个特殊值但逻辑非常统一配合2.2的定义用起来很顺手。验证一下pabacaba时运行结果就是[-1, 0, 0, 1, 0, 1, 2]。3.3 代码里的几个关键细节写这段代码时容易出问题的点我挨个说一下。第一个while循环的边界是i m-1不是i m。因为循环体里i会先自增再赋值最后一次循环i自增后已经是最后一个下标m-1不需要也不应该再计算nxt[m]字符串最后一个位置之后已经没有字符了。如果写成i m数组就越界了。第二个nxt[0]必须单独初始化为-1这是整个回退链的终点。如果没有这个-1当j回退到无路可退时代码会陷入死循环。很多初学KMP的人在这里出问题就是没有理解-1这个哨兵的作用。第三个这个版本求出来的是“基础版next数组”没有做优化。模式串中如果有大量重复字符比如aaaaab基础版next数组在某些场景下会多做几次无意义的回退。优化版通常叫nextval在p[i] p[nxt[i]]时继续回退把指针直接指向最终有效的跳跃位置。面试如果问KMP优化基本都是问这个。建议先把基础版吃透再看优化版否则容易两套逻辑混在一起。4. 完整匹配流程与复杂度分析4.1 匹配主流程代码有了next数组匹配过程就非常简单了。两个指针i遍历主串j遍历模式串主串指针永不回头def kmp_search(s, p): n, m len(s), len(p) if m 0: return 0 nxt build_next(p) i, j 0, 0 while i n: if j -1 or s[i] p[j]: i 1 j 1 if j m: return i - m else: j nxt[j] return -1匹配过程中如果s[i]和p[j]相等两个指针同时前进如果不相等j回退到nxt[j]如果j已经回退到-1说明模式串的头部都对不上当前主串字符此时i前进一位j恢复为0。jm说明模式串完整匹配成功返回起始位置。来模拟一遍。主串sababacabacaba模式串pabacabanxt[-1,0,0,1,0,1,2]。i0时s[0]ap[0]a匹配i1j1。i1时s[1]bp[1]b匹配i2j2。i2时s[2]ap[2]a匹配i3j3。i3时s[3]bp[3]c失配jnxt[3]1此时模式串从位置1开始继续比。i3时s[3]bp[1]b匹配i4j2。i4时s[4]ap[2]a匹配i5j3。i5时s[5]cp[3]c匹配i6j4。之后一路匹配到i9j7jm返回9-72。pabacaba从主串下标2开始确实匹配。4.2 时间复杂度分析KMP的时间复杂度是O(nm)这个结论很多人知道但不知道为什么。关键在于主串指针i在整个匹配过程中只会增加从不回退所以遍历主串的代价是O(n)。而模式串指针j虽然会回退但每次回退都是通过next数组跳转跳转次数不会超过匹配成功的总次数整体也是O(m)级别。两者加起来就是O(nm)。空间复杂度是O(m)主要花在next数组上。相比暴力匹配的O(1)空间多付出了一个模式串长度级别的数组但对于m通常不会太大的实际场景来说这个代价完全可接受。如果模式串很短或者主串和模式串长度差异极大暴力匹配的常数项反而更小KMP的优势主要体现在模式串较长、且主串中频繁出现部分匹配的场景。实际工程里像grep这类工具还会结合Boyer-Moore或Sunday等更快的算法但对于理解字符串匹配的核心思想来说KMP是绕不开的基础课。5. 常见问题与排查5.1 最容易踩的坑第一个坑next数组定义没对上匹配代码直接套用。这是最常见的翻车现场。网上搜KMP代码有的用next[0]-1有的用next[0]0有的数组长度是m有的是m1失配回退时有的写jnext[j]有的写jnext[j-1]。这些代码本身可能都是对的但混着用就全乱了。我建议把一份代码从头到尾吃透包括它用的定义、初始化、回退逻辑然后固定下来其他写法只作为理解参考不要混搭。第二个坑模式串长度为0或1的边界情况。长度为0时直接返回0长度为1时如果匹配到就返回位置匹配不到返回-1next数组只需要处理nxt[0]-1。很多KMP实现忽略了这些边界实际跑起来就报越界。第三个坑返回位置的计算。匹配成功返回的是i-m因为当jm时i已经走到了模式串结束位置的后面起始位置是i减去模式串长度。有人会写成i-j这在某些特殊时候碰巧对但逻辑上不对因为j此时等于mi-j等价于i-m但如果中途有回退i-j就不是起始位置了。第四个坑求next数组时误用了m而不是m-1作为循环边界。这个问题我在3.3节已经提过这里再强调一次它导致的数组越界问题在刷题平台上很容易遇到。5.2 快速排查表现象可能原因排查方法匹配结果多返回了一个位置返回位置写成了i-j1或i-m1用一个小例子手推一遍返回逻辑模式串没匹配到但明明存在next数组和匹配逻辑的定义不匹配检查next[0]初始化和失配回退的代码是否一致死循环或卡住回退链上没有终止哨兵检查nxt[0]是否初始化为-1数组越界build_next循环边界写成im改成im-1确认最后一个位置不赋值匹配正确但next数组和教材对不上教材用的是另一种定义确认是p[0..i-1]还是p[0..i]的最长相等前后缀排查时最有效的办法是拿着小例子手推一遍代码逻辑对不对一目了然。别上来就在大数据集上跑那样只能看到结果错看不到错在哪一步。5.3 一个提高效率的小技巧实际写代码时如果模式串是固定不变的可以把build_next的结果缓存下来避免每次匹配都重新计算。这个优化在处理多段文本搜索同一个关键词时特别明显。另外Python里如果你只是想找一个子串直接用in或find就好内置算法已经很快手写KMP主要用于学习和理解原理或者在某些不能调用内置函数的场景下使用。nextval优化版我也简单提一下它在求next的过程中如果发现p[i] p[next[i]]就把next[i]继续往前跳直到跳到不同的字符为止。这样做的好处是匹配阶段遇到重复字符时能一次跳到位减少无意义的字符比较。代价是预处理阶段多了一点计算但整体收益在模式串重复度高的场景下非常明显。面试题里如果考KMP优化基本就是考这个nextval的构造。我自己的体会是KMP算法第一次学的时候觉得很玄本质上就是把“模式串的自相似性”这张表提前算好用空间换时间。一旦你把next数组的递推过程想明白了后续再看任何字符串匹配算法都会轻松很多。