1. 暴力匹配到底慢在哪一个例子看清失配后的无效位移很多人学KMP之前先接触到的是暴力匹配。写起来很爽一个双重循环搞定但一旦遇上长文本和长模式串性能立刻被打回原形。我当年第一次调一个字符串搜索的需求拿暴力匹配跑一份几十万字符的日志文件肉眼可见地卡顿这才真正体会到KMP存在的价值。先回顾一下暴力匹配的流程主串用指针i遍历模式串用指针j遍历逐字符比较一旦失配就把i回溯到本次匹配起点加一j归零重新比较。这个做法的问题在于主串指针i会反复回溯每次失配都相当于把已经比较过的字符又重新比较了一遍产生大量无效比较。举个例子。主串S ABABABCABABABCABABABC模式串P ABABCABAB。从头开始匹配前5个字符ABABA全部相等第6个位置主串是B模式串是C失配。按暴力做法i退回到第2个位置Bj归0重新从S[1]和P[0]比较发现B≠A继续移位……其实我们已经知道模式串P的前5个字符是ABABA。这5个字符里前缀ABA和后缀ABA是相同的而且长度是3。失配发生在第6个字符说明主串从起点开始的5个字符一定等于模式串的前5个字符。那么主串第4个到第6个字符一定等于模式串第3到第5个字符ABA也就是模式串的前缀ABA。既然前缀已经确认匹配我们完全没必要把j归零重来直接让模式串的指针从j5跳到j3继续匹配就好了。这个跳的操作就是KMP的核心失配时不回溯主串指针i只调整模式串指针j。而j调整的目标就是模式串已匹配部分的前后缀信息。这个信息预先存放在next数组里。所以KMP能解决的问题很简单在处理长文本中重复较多的模式串时暴力匹配存在大量回溯浪费而KMP用空间换时间预处理一个next数组把匹配过程的时间复杂度从O(n*m)降到O(nm)。n是主串长度m是模式串长度。下面所有讨论都围绕一个问题next数组里到底存的是什么怎么算怎么用。只要把这个搞透了KMP基本就通关了。2. next数组的核心定义前缀后缀的最长公共到底怎么理解next数组的教科书定义五花八门网上教程也各说各话很多人就是被不同的定义绕晕的。我先讲最主流的理解方式。对于模式串P定义next[i]为在模式串P中P[0..i-1]这个子串里相等的最长前缀和后缀的长度。请注意下标范围是到i-1不包含P[i]本身。这是一个很关键的点不少教材把next[0]定义为-1把next[1]定义为0原因就在这里。先解释什么是前缀和后缀。前缀对于一个字符串从第一个字符开始到某个位置结束的所有子串但不能包含最后一个字符本身。比如ABABC它的真前缀是A,AB,ABA,ABAB不包括ABABC本身。后缀从某个位置开始到最后一个字符结束的所有子串但不能包含第一个字符本身。同样ABABC真后缀是C,BC,ABC,BABC。相等的最长前缀和后缀指的就是我要找一个最长的长度k使得这个字符串的长度为k的前缀和长度为k的后缀完全相同。比如ABAB前缀有A,AB,ABA后缀有B,AB,BAB。明显前缀AB等于后缀AB长度2所以ABAB的最长相等前后缀长度是2。还可以考虑长度3ABA与BAB不相等。所以最长是2。回到next数组。以经典严蔚敏教材里的定义为例next[j]表示当模式串中第j个字符与主串失配时j要跳转到的位置。当j0时失配主串和模式串都需要移动所以next[0]约定为-1当j1时前面只有一个字符没有真前后缀所以next[1]0。其他情况next[j] 模式串P[0..j-1]的最长相等前后缀长度。举个例子模式串ABABC。next[0] -1next[1] 0因为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[3]1。next[4]P[0..3] ABAB前缀A,AB,ABA后缀B,AB,BAB最长相等的是AB长度2所以next[4]2。记住这个定义后面匹配时你会看到它的威力。还有另一种常见的next数组定义把next[i]定义为P[0..i]这个子串的最长相等前后缀长度包含当前字符并且把next[0]设为0。这种定义在力扣等很多平台上也常见它实际上更接近前缀表概念。两种定义推导出的next数组值会差一位但本质是同一个东西只是下标起点不同。本文后续都以第一种严蔚敏版为准这也是最常见的考研与数据结构课程口径。3. 手工求解next数组从ababc到ababaca一步步推理论归理论动手才算数。我建议所有初学者都在纸上老老实实手工推几次next数组你会在过程中发现规律。3.1 先推一个简单模式串 ababc模式串P ababc长度5。next[0] -1约定next[1] 0子串a无相等前后缀next[2]子串ab前缀a后缀b不等next[2]0next[3]子串aba前缀{a,ab}后缀{a,ba}相等最长是a长度1next[3]1next[4]子串abab前缀{a,ab,aba}后缀{b,ab,bab}相等最长ab长度2next[4]2所以next数组 {-1, 0, 0, 1, 2}。验证一下匹配场景。主串S ababcababx模式串P ababc。匹配到i4时P[4]cS[4]c匹配i5P[5]越界实际上模式串全部匹配i指向b此时匹配成功结束。如果主串是ababaababx呢前4个abab匹配第5个位置S[4]aP[4]c失配。暴力做法i回溯到1从头来。KMP做法j next[4] 2。i不动继续比较S[4]a和P[2]a相等继续。你看i没有回退只把j从4跳到了2完美利用了abab的前后缀知识。3.2 再推一个复杂模式串 ababaca模式串P ababaca长度7。这个串在各大教材和面试题里出境率很高一定要会算。next[0] -1next[1] 0anext[2] 0aba≠bnext[3] 1aba最长公共前后缀a长度1next[4] 2abab最长公共前后缀ab长度2next[5] 3ababa前缀{a,ab,aba,abab}后缀{a,ba,aba,baba}最长公共是aba长度3next[6] 0ababac前缀{a,ab,aba,abab,ababa}后缀{c,ac,bac,abac,babac}没有任何一个相等所以是0最终next数组为{-1, 0, 0, 1, 2, 3, 0}。注意next[6]为什么不是4ababa和ababac的后缀你需要硬凑后缀里最后一个字符是c而前缀最后一个字符分别是a,b,a,b,a跟c都不沾边所以最常见的前后缀匹配方式全都失效只能是0。我再给你一个易错点求next时比较的是子串内部的前缀和后缀不要拿整个模式串跨位置去理解。很多同学写代码时j回溯来回溯去最后忘了求next[i]时只依赖已经算出来的next[0..i-1]导致逻辑混乱。3.3 一眼看穿next数组的递推关系手工算能建立直觉写代码就必须提炼递推关系了。设我们已经求出了next[0..i-1]现在要求next[i]。用j表示当前已匹配的前后缀长度。初始时i1时j next[0] -1通常代码里统一处理为j -1。根据定义next[i]是在子串P[0..i-1]中找最长相等前后缀。如果P[i-1] P[j]这里j是上一个状态的最长前后缀长度也就是正在比较的下一个字符位置那么直接在之前的基础上加1即next[i] j1。如果不相等就需要让j回退到next[j]继续比较直到相等或者j -1。为什么是j next[j]因为当前前缀和后缀分别都是P[0..j-1]的延伸一旦延伸失败我们就要在已经匹配的这一段里找更短的公共前后缀这正是next[j]所表示的跳转位置。你品品这个操作是不是和失配时模式串自身跳转一模一样所以求next的过程本质上是模式串自己和自己做KMP匹配。我在下一节展开。4. 求解代码的编写逻辑让模式串自己和自己匹配很多初学者看代码能看懂但不知道为什么这么写。我先把标准实现贴出来再逐步拆解。void getNext(const char* P, int next[]) { int m strlen(P); int i 0; // 当前要求next[i]的模式串下标 int j -1; // 已经匹配的前缀长度初始化为-1 next[0] -1; // 约定 while (i m) { if (j -1 || P[i] P[j]) { // 两种情况需要推进 // 1. j -1说明前缀走到头了仍不匹配只能从头开始 // 2. P[i] P[j]当前字符可以继续延伸匹配 i; j; next[i] j; } else { // 匹配失败j回退到之前已经匹配过的前缀中 j next[j]; } } }这个循环在i小于模式串长度时运行i从0开始每次成功匹配或j为-1时i和j都加1并记录next[i]。最终循环结束后next[0..m]共m1个元素都被赋值但通常我们只用next[0..m-1]因为next[m]在实际匹配中用不到模式串完全匹配时不会失配。为了代码简单数组长度会多分配一个。4.1 逐行拆解自己和自己匹配这句话看这个过程最有意思的是P[i]和P[j]的比较i相当于主串指针但这个主串其实是模式串本身j相当于模式串指针用来匹配模式串的前缀。当P[i] P[j]时说明前缀P[0..j]和后缀P[i-j..i]已经相等于是j向前扩展一位。此时next[i1]就等于扩展后的j。因为next[i1]对应的是P[0..i]的最长公共前后缀长度而P[i]正好是在原基础上新增的最后一个字符。当P[i] ! P[j]时说明当前扩展失败我们需要寻找更短的相等前后缀。这里的逻辑和匹配阶段失配一样既然已经知道P[0..j-1] P[i-j..i-1]那么在这个已匹配的部分中最长公共前后缀长度是next[j]所以j跳到next[j]再试。如果一直跳最后j变成-1说明没有任何更短的前后缀只能让i前进j从0开始。很多同学困惑的点是为什么j -1时也进入i;j;因为j为-1表示连第一个字符都和当前后缀对不上意味着P[i]没法作为后缀的尾字符那么P[0..i-1]没有非空的公共前后缀next[i]只能记为0。执行i; j;后j变为0next[i]记录为0开始处理下一个字符非常自然。4.2 用一个例子验证代码流程以ababaca为例我们模拟一下循环最关键的几步。初始化i0, j-1, next[0]-1。i0, j-1进入j-1分支i1, j0next[1]0。i1, j0P[1]bP[0]a不匹配jnext[0]-1。i1, j-1进入j-1分支i2, j0next[2]0。i2, j0P[2]aP[0]a匹配i3, j1next[3]1。i3, j1P[3]bP[1]b匹配i4, j2next[4]2。i4, j2P[4]aP[2]a匹配i5, j3next[5]3。i5, j3P[5]cP[3]b不匹配jnext[3]1。i5, j1P[5]cP[1]b不匹配jnext[1]0。i5, j0P[5]cP[0]a不匹配jnext[0]-1。i5, j-1进入j-1分支i6, j0next[6]0。i6此时循环条件imm7成立P[6]aP[0]a匹配i7, j1next[7]1。注意这里next[7]算出来了但实际匹配时不会用到。最终数组{-1, 0, 0, 1, 2, 3, 0}和我们手工算的一致忽略next[7]。4.3 一个极易踩的边界问题上面代码里的i; j; next[i] j;采用先自增再赋值的方式下标交错处理稍不注意就会数组越界。比如当im-1时如果P[m-1]匹配成功i后i变成m再next[i] j会写越界。所以务必将next数组长度声明为m1或者更保险直接m2。实际匹配阶段只需要next[0..m-1]但求解阶段为防越界多留一位是通用做法。另外刚才的代码在i m - 1时还会继续循环一次因为while条件i m在最前面判断进入循环体的是im-1所以即使边界的P[m-1]匹配成功写next[m]也是安全的。有的写法用for循环边界更要小心。5. 匹配阶段如何回退i主串、j模式串的正确操作好了next数组算出来了接下来就是用它来做真正的匹配。这一部分的代码写法差异不大但很多人一开始会把i和j的关系搞混尤其是失配时i要不要动。我先把完整匹配流程写出来。int kmpSearch(const char* S, const char* P, int next[]) { int n strlen(S); int m strlen(P); int i 0; // S 的指针 int j 0; // P 的指针 while (i n j m) { if (j -1 || S[i] P[j]) { i; j; } else { j next[j]; } } if (j m) { return i - j; // 返回起点下标 } return -1; }注意这个循环中主串指针i永远只增不减只有在j-1或匹配成功时前进。失配时执行j next[j]i停在原地等待继续比较。5.1 最关键的步骤演示S abcababcabx, P abcabx先用一个经典例子走一遍匹配流程。模式串P abcabx先求next数组手算一下{-1, 0, 0, 0, 1, 2}。过程i0,j0S[0]aP[0]a匹配i1,j1。继续匹配到i4,j4时比较S[4]a和P[4]a匹配i5,j5。S[5]bP[5]x失配。此时j5查next[5]2所以j跳到2i保持5。比较S[5]b和P[2]c失配jnext[2]0。比较S[5]b和P[0]a失配jnext[0]-1。j-1进入if分支i6,j0。继续匹配S[6]aP[0]a匹配最终在i9时j6匹配完成返回起点9-63。可以验证主串从下标3开始是abcabx完全匹配。在这个过程中主串指针i从0走到9从未回退这就是KMP的核心优势。5.2 为什么失配时要 j next[j]而不是别的想通这个问题KMP就彻底通了。失配发生时主串的i位置之前从i-j到i-1这j个字符一定等于模式串的前j个字符P[0..j-1]。现在我们希望找到一个更小的k使得模式串的前k个字符和主串当前i位置之前的k个字符相等这样我们就能保持i不动用模式串的第k个字符去和主串i位置比较。由于主串这段字符与P[0..j-1]完全相同所以问题等价于在P[0..j-1]中找一个最长且等于P[0..k-1]的后缀。这正是next[j]的定义。所以j跳到next[j]是唯一正确的选择。这里有人会问那为什么不能是j next[j-1]因为next数组有两种定义如果你采用的是next[i]表示P[0..i-1]的最长公共前后缀长度且next[0]-1那么失配在j位置时要找的正是P[0..j-1]的公共前后缀所以用next[j]。如果你采用的是另一种前缀表定义next[i]表示P[0..i]的最长公共前后缀长度那么失配在j时你要用next[j-1]。这就是网上代码让人眼花缭乱的根本原因。选定一种定义把匹配代码和定义严格对应不要混着用。5.3 匹配过程中next[m]用不了正常有人会问求解next时最后算出了next[m]为什么匹配时用不上因为匹配成功的条件是j m此时整个模式串匹配完成不需要再失配跳转。只有匹配尚未完成时的失配才需要next而失配发生在0 j m之间所以next[0..m-1]就够了。如果是想找出所有出现位置匹配成功后可以用j next[m]继续寻找下一个匹配这时next[m]就有用了。比如Patternabab匹配成功一次后j跳到next[4]2意味着复用已经匹配的ab前缀继续向后找能避免重叠匹配遗漏。不过这是进阶用法初学先把基本匹配搞懂。6. next的改进版nextval为什么有些教材的答案不一样如果你上网搜KMP的next数组会发现有的博客给的答案和课本不一样。比如模式串abab按照前面定义算next {-1, 0, 0, 1}但有些教材会告诉你next {-1, 0, -1, 0}它实际是next数组的改进版通常叫nextval数组。6.1 nextval解决的问题考虑一个极端场景模式串aaaaab主串aaaaaacdef...。按原始next数组计算next {-1, 0, 1, 2, 3, 4}匹配时假设j5P[0..4]aaaaa都匹配此时P[5]b和主串失配。查next[5]4j跳到4继续比较P[4]a和主串那个失配字符大概率还是失配然后j跳到next[4]3P[3]a还是失配……每一次失配都要多跳一次比较这跟暴力法退着比较有点类似虽然i没回溯但j的跳转效率低了。仔细看根源在于失配时j跳到的那个位置上字符正好还是那个和主串已失配的相同字符。既然P[j]和P[new_j]一样即使跳到new_j也不可能匹配成功那这个跳转就是无效的。6.2 nextval的优化逻辑改进思路非常直白当next[j]指向的字符P[next[j]]与P[j]相同时把next[j]换成next[next[j]]一直到不等或到达边界为止。代码可以这样写void getNextval(const char* P, int nextval[]) { int m strlen(P); int i 0, j -1; nextval[0] -1; while (i m) { if (j -1 || P[i] P[j]) { i; j; // 改进核心如果P[i] P[j]则继续递推 if (i m P[i] ! P[j]) { nextval[i] j; } else { nextval[i] nextval[j]; // 注意j此时已经是i对应的最长前后缀长度需要再跳 } } else { j nextval[j]; } } }注意这样求出来的nextval数组当P[i]P[j]时会继续往前跳到nextval[j]。很多教材通过先求出原始next再额外扫一遍做去重处理得到的也是同一个结果。6.3 对比两种数组模式串原始next改进nextvalabab{-1, 0, 0, 1}{-1, 0, -1, 0}aaaaa{-1, 0, 1, 2, 3}{-1, 0, 0, 0, 0}改进后的数组在某些场景如大量重复字符下能明显减少无意义的比较次数但时间复杂度依然是O(nm)级别。面试和考试中如果题目明确说next数组通常指原始定义如果提到nextval或改进的KMP再按改进版处理。做题前务必先确认题目语境。7. 实际刷题与考试中的常见坑下标起点、循环边界和差异对比最后聊点实战中的体会。KMP在很多人的算法复习清单里属于学的时候痛苦考完就忘的内容但只要你踩过下面几个坑印象会非常深。7.1 下标从0开始还是从1开始这是最坑的。考研教材严蔚敏版为了说明方便常采用模式串下标从1开始P[0]不存字符或作为哨兵next[j]表示第j个字符失配时跳到第next[j]个字符这样next数组整体平移不再有-1。而程序员写代码更习惯C风格的0起始下标。这就是同一个KMP有两种代码形态的原因。如果你在牛客或力扣上刷题遇到KMP相关题目先看它给出的next数组示例是哪种。比如LeetCode 28题找出字符串中第一个匹配项的下标直接手写一个0起始的KMP即可不需要纠结教材定义。如果是考试笔试题要求写next或nextval题目样例里的值会明确提示用哪种定义照着样例对齐。7.2 一个隐蔽的越界和死循环问题在编写getNext时最容易出现的bug是死循环。典型错误是while (i m) { if (P[i] P[j]) { i; j; next[i] j; } else { j next[j]; // 如果j初始为0且P[0] ! P[i]这里会死循环 } }如果j从0开始P[0]与P[i]不相等时j next[0]。如果next[0]不是-1而是0就会陷入无限循环。解决办法就是保证next[0]-1并让j-1作为一个单独分支。这也是我强烈建议你写j -1初始化的原因。-1不是多此一举它是从结构上避免死循环的关键哨兵。7.3 实战练习建议KMP的经典应用不止字符串匹配。数组循环移位判断、字符串周期判断、重复子串检测、正则表达式简化版匹配等都能用到它。我建议按这个顺序练习手算next拿ababc、abcabc、aaaa这几个串练到脱口而出。手写getNext和search要求一遍编译通过。做LeetCode 28题确保两种定义都能写出。不用库函数进阶看LeetCode 459题重复的子字符串用KMP判断一个字符串是否由重复子串构成这里要用到next[m]代表整串最长公共前后缀的巧妙性质。再看找出所有匹配位置实现锻炼next[m]的用法。做完这五步KMP基本不会再有盲区。7.4 我的个人体会从我刷了几百道字符串题的经验看KMP其实不靠背代码靠的是理解next[j]的物理意义失配位置之前模式串里面最长的、可复用的前后缀。当你觉得代码记不住时就在纸上画一个主串窗口和模式串窗口失配时想一想模式串怎么能挪动得最合理next数组自然就推出来了。最后再分享一个调试技巧写完KMP后用一个极端的测试用例验证比如主串全a模式串全a但结尾一个b这样可以同时测试大量有效跳转和最终失配的情况。再试主串aaaab模式串aaab这种前缀重复度高的用例。如果你能保证这些用例下程序行为正确基础部分基本稳了。KMP是个越磨越清楚的东西多推几次你会喜欢上这种用预计算换取运行效率的思维。