先交代一个自己的黑历史大一学数据结构时KMP算法我一连听了三遍都没听懂每次都在“next数组到底怎么算”那里卡住。后来刷题刷到字符串匹配相关的题发现不会KMP就像不会用二分查找一样心里没底。直到某天静下心把next数组的推导过程用手写模拟了三遍才真正有一种“通了”的感觉。这篇笔记就是基于那段时间的反复整理把KMP算法的来龙去脉、next数组的计算口诀、完整代码模板以及我踩过的若干坑一次性讲清楚。这篇文章适合正在学数据结构与算法的在校生、准备面试的求职者以及所有在LeetCode等题库刷到“实现 strStr()”“重复子字符串”等问题时想彻底搞懂KMP的同学。看完之后你能手推next数组能写出标准的KMP匹配代码也能跟面试官解释清楚“为什么KMP是O(mn)”而不是O(m*n)。1. KMP算法到底解决了什么问题1.1 朴素字符串匹配的痛点先看最朴素的字符串匹配思路给定一个主串s和模式串p要在s中找到p出现的位置最简单的方法就是“暴力移位”——s的每个位置都尝试一次以该位置为起点逐个字符跟p去比较。一旦发现中间某个字符不匹配就把起点向后移一位再从p的第一个字符重新开始。这个方法好理解但效率有时候非常难看。比如主串是AAAAAAAAAB模式串是AAAAB从s的第一个位置开始每次都要比到模式串倒数第二个字符才发现不匹配然后只敢向后挪动一格整体的时间复杂度是O(m*n)其中m是主串长度n是模式串长度。在长文本的场景下这种效率完全没法接受。这里有一个被很多人忽略的关键点朴素算法每次匹配失败后只向后移动一位但前面已经比对过的信息全部被丢弃了。实际上这些“已匹配字符”里面隐藏着大量可复用的信息。KMP算法的核心就是把这些信息利用起来——它不是在主串上“跳过”字符而是在模式串上做“聪明地回退”让匹配过程整体保持主串指针不回退。1.2 KMP的直觉利用部分匹配结果我打一个比较生活化的比方。假设你在读一本英文小说要找“performance”这个词。当你已经在正文里看到了“perfor”这几个字母接下来一个字符是“x”那么你心里已经清楚这次匹配失败但前面已读到的“perfor”并非完全没用——你不需要把目光退回这一段的最开头重新读。为什么因为你已经积累了“perfo”这个词根信息你知道下一轮可以从某个位置继续尝试而不是傻傻地退回去。KMP算法正是把这种“我知道已经配过哪几个字符”的感觉量化成一个表这个表就是next数组。它预先处理模式串计算出“当模式串第j位匹配失败时模式串应该退回到哪个位置继续匹配”。有了这张表主串的指针一路向前从不回头整体时间复杂度降到O(mn)。2. next数组是KMP的心脏2.1 前缀、后缀与最长相等前后缀要说清楚next数组绕不开三个概念前缀、后缀、最长相等前后缀。这个概念是整个算法的地基必须真正吃透。对于一个字符串前缀是指从第一个字符开始、但不包含最后一个字符的所有子串后缀是指以最后一个字符结尾、但不包含第一个字符的所有子串。拿ababc举例它的前缀有a、ab、aba、abab它的后缀有c、bc、abc、babc。“最长相等前后缀”就是前缀集合和后缀集合的交集中长度最长的那个。继续以ababc为例前缀中有ab后缀中也有ab所以它的最长相等前后缀长度是2。注意a虽然是前缀也是后缀但长度只有1不是最长的abc出现在后缀中但不在前缀中所以不算。这里要特别提醒一个容易混淆的点最长相等前后缀不能等于字符串自身。也就是说在算整个模式串的最长相等前后缀时不能把整串当做自己的前缀或后缀来计算。这是很多初学KMP时算错next值的第一个坑。2.2 next数组的含义两种常见口径next数组到底存什么市面上有两种主流的定义。一种是考研数据结构教材里的经典定义下标从1开始next[1]0next[j]表示模式串的第j个字符发生不匹配时应该用第几个字符重新比较。另一种是程序设计竞赛和LeetCode题解中常见的下标从0开始的版本next[i]表示前i1个字符组成的子串的最长相等前后缀长度减1或者某些写法直接存最长相等前后缀长度。两种定义并不矛盾只是映射关系不同。我强烈建议初学者先彻底掌握其中一种不要混着学否则很容易被网上的代码搞晕。我个人比较推荐下标从1开始、next[1]0的经典教法因为它的语义最贴近“模式串指针往哪跳”的直觉也最容易手算验证。后面我会把两种口径都写出来方便大家对照。2.3 手算next数组的实操方法先给出手算的经典步骤。假设模式串是下标从1开始的字符串p[1..n]初始化next[1]0这个值是固定写死的边界条件。令j0i1然后让i从2遍历到n递推求解next[i]。递推的核心规则是这样的假设当前已经知道了next[i-1]k说明p[1..k-1]和p[i-k..i-1]是匹配的。接下来要看p[k]和p[i-1]是否相等如果相等那么next[i]next[i-1]1。如果不相等就把k回退到next[k]继续比较直到k0或找到某个位置使字符相等。我拿实际例子走一遍模式串为ababc下标从1开始第1位next[1]0。第2位看p[1]a与p[1]不这里的i2j0比较p[j1]和p[i]即p[1]a和p[2]b不等且j已经是0所以next[2]0。第3位jnext[2]0比较p[1]a和p[3]a相等j变为1next[3]1。第4位此时jnext[3]1比较p[2]b和p[4]b相等j变为2next[4]2。第5位此时jnext[4]2比较p[3]a和p[5]c不等于是j回退到next[2]0再比较p[1]a和p[5]c还是不等j保持0next[5]0。最终得到next数组为0,0,0,1,0等一下实际手算结果是next[1]0, next[2]0, next[3]1, next[4]2, next[5]0。拿到next数组之后匹配时如果模式串第j位匹配失败就用jnext[j]回退。例如匹配到第5位失败时模式串直接跳回第0位相当于从头再来。2.4 快速计算next的两种实用技巧手算太慢这里分享两个我常用的快算技巧尤其适合做题和面试手撕代码前的心算。技巧一直接按“最长相等前后缀”求。对p[1..j]这j个字符肉眼找最长相等前后缀长度这个长度就是next[j]。比如abab前缀ab和后缀ab相等长度2那么next[4]2。这个方法虽然看起来不够“算法”但在手算时比递推快得多而且不容易出错。技巧二如果题目要求的是“前缀函数”LeetCode常用的版本比如prefix[i]表示p[0..i]的最长相等前后缀长度那它和经典next有一个换算关系经典next[j]下标从1开始在数值上等于下标从0开始时前j-1个字符的前缀函数值加1或者说经典next[j]prefix[j-2]1当j≥2时。初学者可以不用死记这个公式但看到不同的代码风格时心里要有数。2.5 next数组的代码实现两种风格对照下面给出经典风格的代码语言是C风格但改成其他语言也没有难度// 下标从1开始p[0]不用n是模式串长度 void getNext(string p, vectorint next) { int n p.size() - 1; // 假设p已经转成下标从1开始的字符串 next.assign(n 1, 0); for (int i 2, j 0; i n; i) { while (j 0 p[i] ! p[j 1]) { j next[j]; } if (p[i] p[j 1]) { j; } next[i] j; } }再看竞赛/LeetCode常用的前缀函数风格// 下标从0开始p是原始模式串 vectorint prefixFunction(string p) { int n p.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 p[i] ! p[j]) { j pi[j - 1]; } if (p[i] p[j]) { j; } pi[i] j; } return pi; }两段代码的本质逻辑完全一致只是下标边界不同。用哪种风格不重要重要的是能默写出来并且知道每个变量在当前代码里的含义。3. KMP匹配全过程与代码模板3.1 匹配时的指针移动逻辑有了next数组匹配阶段就很机械了。定义两个指针i指向主串sj指向模式串p。初始化i1,j1下标从1开始的情况下。循环比较s[i]和p[j]如果相等ij继续比较下一对。如果不等且j1则jnext[j]i不变继续比较。如果不等且j1说明模式串第一个字符都配不上了此时i重新开始。当j越过模式串长度n说明匹配成功返回i-n作为起始位置。如果i遍历完主串还没有匹配成功返回-1。这里有一个很多初学者会纠结的问题为什么匹配失败时主串指针i不用回退原因很简单next数组保证的是当p[j]与s[i]失配时模式串的前next[j]-1个字符已经和s[i-1]往前数的那几个字符匹配上了。也就是说虽然j往回跳了但主串已经比对过的部分没有被浪费i自然不需要倒退。3.2 完整模板下标从1开始// 返回模式串在主串中第一次出现的位置不存在返回-1 int kmpSearch(string s, string p) { int m s.size(), n p.size(); s s; // 下标从1开始 p p; vectorint next(n 1, 0); // 求next for (int i 2, j 0; i n; i) { while (j 0 p[i] ! p[j 1]) { j next[j]; } if (p[i] p[j 1]) { j; } next[i] j; } // 匹配 for (int i 1, j 0; i m; i) { while (j 0 s[i] ! p[j 1]) { j next[j]; } if (s[i] p[j 1]) { j; } if (j n) { return i - n; // 找到匹配的起始位置 } } return -1; }这个模板我在笔试和面试中至少手写过几十次几乎零改动的场景非常多。它的好处是把next数组和匹配过程写到同一个函数里逻辑紧凑不容易在跳转时出现下标错误。3.3 完整模板下标从0开始再给出LeetCode风格的模板方便直接应对在线笔试int strStr(string s, string p) { int m s.size(), n p.size(); if (n 0) return 0; vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 p[i] ! p[j]) { j pi[j - 1]; } if (p[i] p[j]) { j; } pi[i] j; } int j 0; for (int i 0; i m; i) { while (j 0 s[i] ! p[j]) { j pi[j - 1]; } if (s[i] p[j]) { j; } if (j n) { return i - n 1; } } return -1; }这段代码在很多题库里可以直接当作“实现strStr()”的答案。注意空模式串时单独处理返回0这是题目的惯用规定。3.4 复杂度分析为什么是O(mn)KMP的时间复杂度包含两部分求next数组的过程和匹配过程。求next时外层循环i从2到n每次循环内部可能有多次jnext[j]的回退。表面上看起来像是嵌套循环但仔细分析会发现j增加的总次数不会超过n因为每次循环最多让j增加1而回退时j是变小的所以总回退次数不超过总增加次数。因此求next的时间复杂度是O(n)。匹配过程同理外层i遍历主串一次j增加的总次数不超过m回退次数也不超过增加次数所以匹配阶段是O(m)。两个阶段加起来是O(mn)。这个复杂度证明可以用“势能法”去理解不用背严谨的数学推导但要能跟人讲清楚程序里看起来有while但总操作次数是线性级别的不是平方级别。3.5 一个完整的运行示例拿一个具体的例子验证整个流程。主串ABABABC模式串ABABC下标从1开始。先求模式串ABABC的next数组。用快算法j1子串A固定next[1]0。j2子串AB最长相等前后缀0。j3子串ABA前缀A后缀A最长相等前后缀1。j4子串ABAB前缀AB后缀AB最长长度2。j5子串ABABC前缀ABAB后缀BABC最长前后缀前缀A和后缀C不匹配0。next数组0, 0, 1, 2, 0。匹配过程i1s[1]Ap[1]A匹配i2j2。i2s[2]Bp[2]B匹配i3j3。i3s[3]Ap[3]A匹配i4j4。i4s[4]Bp[4]B匹配i5j5。i5s[5]Ap[5]C不匹配jnext[5]0。重新比较s[5]A和p[1]A匹配j2i6。i6s[6]Bp[2]B匹配j3i7。i7s[7]Cp[3]A不匹配jnext[3]1。比较s[7]C和p[1]A不匹配jnext[1]0。i8越界匹配失败。咦这里看起来好像没有匹配成功原因是我刻意选了一个在主串里确实没有匹配位置的例子。大家可以自行换一组数据验证成功的情况比如主串ABABABABC模式串ABABC同样流程在第6步附近就能匹配成功。手推一遍成功和失败各一例对理解KMP至关重要。4. 常见问题与排查技巧实录4.1 死循环还是跳错位置很多人在写KMP时遇到最诡异的问题就是匹配过程进入了死循环。排查思路通常集中在while循环里。比如这段代码while (j 0 s[i] ! p[j 1]) { j next[j]; }如果next[j]j也就是next数组某个位置和自己相同那么一旦进入while就会出不来。这种情况几乎都是next数组求错了。检查时重点看next[1]是否被错误设置成了1经典定义必须从0开始。另一个高频问题是p[i] ! p[j1]这类的下标比较很多人会把j1误写成j导致比较的字符位置错位。这种错误不会报错而是表现为匹配结果完全错误。建议在关键比较语句前后加打印逐位输出当前i、j、s[i]、p[j]一眼就能定位。4.2 next[1]应该等于0还是1这要看你用的是哪种定义。下标从1开始的经典定义next[1]0下标从0开始的前缀函数版本pi[0]0。两个都是0但语义完全不同。经典定义里0表示“模式串已经彻底没有位可以退了主串要前进”前缀函数里0表示“当前位置之前的字符串没有相等前后缀”。如果面试官让你手推next数组建议先问清楚他期望哪种口径。如果对方不明确你可以主动说明“我用下标从1开始的经典定义next[1]0”这样双方就对齐了后面怎么答都不会被扣分。4.3 用KMP求子串出现次数KMP不仅能找第一次出现的位置还能统计模式串在主串中出现的次数。在每次匹配成功后只需要让jnext[j]而非置零重新开始就能继续扫描主串统计重叠或不重叠的匹配次数。比如统计重叠出现次数时匹配成功后执行jpi[j-1]前缀函数版本然后继续循环。这个技巧在处理“统计某些模式出现频率”的题目里非常常用而且在此基础上可以延伸出“求最长重复子串”“字符串周期”等进阶问题。4.4 网站与题库实战建议题库里的经典题目我基本都刷过一遍这里列几个值得反复做的LeetCode 28实现strStr()直接套用KMP注意空串特判。LeetCode 459重复的子字符串此题解法之一是先用前缀函数求整个字符串的最长相等前后缀再判断n - pi[n-1]是否能整除n。洛谷P3375【模板】KMP可以用它检验自己的模板在严格数据下是否健壮。剑指Offer 20牛客版/ 表示数值的字符串这题虽然不完全是KMP但可以练习状态机思维。我个人的刷题顺序建议是先手算10个模式串的next数组再默写一次匹配模板最后通过LeetCode 28和459加深理解。不要一上来就刷难题KMP这道坎主要卡在理解上理解通了后面是水到渠成。4.5 面试现场怎么讲KMP面试手撕KMP时很多人的崩溃不是不会写而是紧张之下忘记边界条件。这里分享一个我总结的“三句话”开场结构帮你在面试官面前组织语言第一句话KMP解决字符串匹配的重复比较问题核心是预处理模式串得到next数组。第二句话next数组的含义是最长相等前后缀它告诉我们失配时模式串能跳到哪个位置。第三句话匹配时主串指针不回退时间复杂度O(mn)。这三句话说完面试官一般就能判断你确实理解了KMP的本质。接着写代码时注意先把空串特判、下标边界写清楚再写求next和匹配两个循环。我个人经验是手写时先用注释把两个阶段标出来能明显降低出错率。4.6 补充KMP的经典演进与变体KMP算法不是孤立的知识点它还引出了一系列变体和延伸。比如扩展KMPEx-KMP可以求主串每个位置与模式串的最长公共前缀Z算法也解决类似问题和KMP有很多相通之处。理解好KMP的“前后缀”核心再去看Z算法会觉得非常自然——Z数组维护的也是前缀匹配信息只是求解顺序和表现形式不同。还有一个高频变体是“循环节判定”。给定一个字符串判断它是否由某个子串重复构成核心就是利用前缀函数数组最后一个值pi[n-1]。设字符串长度为nlen n - pi[n-1]如果n % len 0则原串可以由长度为len的子串重复构成。这个结论我自己推过一遍本质是基于最长相等前后缀和周期性的关系理解了之后不用背结论。我个人的体会是KMP是那种“理解门槛高但突破之后收益极大”的算法。它培养的“利用已匹配信息避免重复计算”的思维在后面学Boyer-Moore、Rabin-Karp、AC自动机时都会反复用到。最后再分享一个小技巧如果你在面试或考试中突然忘记next数组具体怎么算别慌直接把模式串的前缀函数口算出来再通过“前缀函数值加1”的方式映射回经典next这样至少不会让逻辑断层还能让面试官看到你有系统的知识网络。相信我把这篇笔记里的例子手推一遍KMP就再也没有秘密了。