1. 从一道字符串匹配题说起KMP到底解决了什么问题如果你刷过数据结构与算法的字符串章节大概率逃不开KMP算法这个名字。我第一次接触它的时候是在某高校的数据结构课上老师板书写了一大黑板next数组推导底下一片茫然。后来自己工作之后在日志分析、文本检索、编辑器查找功能这些实际场景里又反复碰到字符串匹配问题才真正理解KMP设计的精妙之处。KMP的全称是Knuth-Morris-Pratt算法由三位计算机科学家联合提出。它的核心任务是解决在一个目标串中查找模式串首次出现位置的问题也就是字符串匹配。在Java里对应indexOf在C语言里对应strstr在文本编辑器里对应“查找”功能。你每天用的按键查找背后都是这类算法在跑。在KMP之前最朴素的匹配方法是暴力搜索模式串从目标串的每一个位置开始逐个对齐、逐字符比较。它的问题非常明显——一旦在模式串的中间某个位置失配已经辛辛苦苦比较过的部分就全部作废模式串老老实实右移一位重新从头开始比。如果目标串是AAAAAAAAAAAB模式串是AAAAB前9次匹配你都比到了最后一个字符才失败每次都白干时间复杂度直接变成O(m×n)。KMP的核心思路则是失配的时候主串的指针i不要回退而是利用已经匹配部分的信息让模式串的指针j聪明地回退到一个安全位置。这个“安全位置”不是拍脑袋想的而是通过预处理模式串生成一张next数组来决定。做到这一点之后匹配阶段的时间复杂度稳定在O(n)预处理阶段O(m)整体O(mn)。这篇文章会从零开始把KMP按“为什么要这么做→next数组怎么来的→代码怎么写→踩过哪些坑”的顺序完整拆一遍最后附上我实际调试过程中的心得。不管你是期末突击还是准备面试手撕KMP照着这个思路走一遍应该能比当年课堂上的我少走不少弯路。2. 暴力匹配的死穴与KMP的破局思路2.1 暴力匹配为什么慢一次一次“从头再来”先看暴力匹配的逻辑。假设目标串s是ABABABCABAB模式串p是ABABC。暴力匹配的流程是这样的第一轮ABABABCABAB ABABC 前4个字符ABAB都匹配第5个字符A和C失配 第二轮ABABABCABAB ABABC 模式串右移一位A对B失配直接失败 第三轮ABABABCABAB ABABC 前3个字符ABA匹配第4个字符B和A失配 第四轮ABABABCABAB ABABC 第一个字符就失配...看到问题了吗第一轮我们已经知道目标串前4个字符是ABAB但第二轮还要重新拿模式串的第1个字符去和目标串的第2个字符比第三轮又从头比。这些比较绝大多数是重复劳动因为上一轮失配时已经告诉你目标串该位置的字符集长什么样了你却没有利用这个信息。这个问题的本质是暴力匹配把“模式串”看成完全孤立的信息失配后只能机械地右移一位信息利用率极低。当最坏情况出现每次都是最后一个字符失配时复杂度就是O(m×n)比如sAAAA...AAB、pAAA...AAB这种结构直接卡成灾难。2.2 KMP的破局视角失败本身也携带信息KMP想通了一个关键点模式串在某个位置失配说明从起点到失配位置的前一个字符和目标串中对应的这一段是完全匹配的。这一段匹配成功的字符串本身就携带了关于“模式串该往右滑多远”的信息。举一个更直观的例子。模式串ABABC假设在主串的某个位置已经匹配到ABAB前4个字符都对了第5个字符失配。此时已知条件有两个模式串的前4个字符ABAB和主串的对应4个字符完全一致主串中这4个字符的下一个位置不是模式串的第5个字符C。那么模式串能不能直接右移一位去对比第2个字符能但没必要。因为ABAB这个串里前缀AB和后缀AB是相等的。也就是说主串中这一段的后两个字符AB恰好是模式串的前两个字符AB。既然主串后两个字符已经被验证过了模式串直接右移到让前两个字符AB对齐主串这两个位置就能跳过一部分必然失败的对齐尝试。这个思路的本质是从失配点往前看一段已匹配的前缀找到它最长的“既是前缀又是后缀”的部分这个长度就是下一次匹配时模式串可以保持对齐的位置。这个“最长相等前后缀长度”就是KMP算法的灵魂也是next数组的来源。2.3 前缀、后缀和最长公共前后缀这里需要把几个名词彻底搞清楚。前缀指的是字符串从开头开始、但不包含最后一个字符的任意子串后缀指的是从某个位置到串尾、但不包含第一个字符的任意子串。比如ABAB前缀集合A、AB、ABA后缀集合B、AB、BAB公共前后缀A、AB最长公共前后缀记为PMT值AB长度为2注意边界条件整个字符串本身不算前缀或后缀否则一个串的最长公共前后缀永远是它自己那算法就没意义了。为了把公共前后缀的含义一次说清我习惯用一个通俗类比。想象你要把一根绳子从中间剪开让左边的起点和右边的终点出现相同的花纹图案。最长公共前后缀就是“在不把整根绳子都用上的前提下你能找到的最长一组左右呼应的花纹”。KMP把模式串每一段前缀字符串的这个值都算出来就形成了一张关键表格。3. next数组的完整推导用手算再用代码算3.1 next数组的定义与两种教材风格的差异网上的KMP教程有一个让无数初学者崩溃的问题next数组有两种定义方式不同教材下标基准不一样代码对不上就全盘皆输。严谨来说这里涉及PMTPartial Match Table部分匹配表和next数组的关系。PMT[i]表示模式串前i1个字符即p[0..i]中最长公共前后缀的长度。而KMP匹配时失配后j回退的位置往往用的是PMT[j-1]。于是教材A把next[i]直接定义为PMT[i-1]的值对应“右移一位”的写法教材B把next[i]定义为PMT[i]刷题平台和面试场合两种写法都出现过。为了避免混淆我这里给出一种最直观、最容易和手写推导结果对照的约定定义next[j]当模式串第j个字符下标从0开始失配时j应该回退到的位置。特殊地next[0] -1表示第一个字符就失配时主串i要前进一位、模式串j停在0。这套定义下next[j]的值等于p[0..j-1]这个子串的最长公共前后缀长度。也就是说失配时要查看“匹配好的前j个字符”的PMT值把j回退到那个位置。3.2 手算推演以“ABABCABAB”为例我强烈建议你动手推一遍比看十遍公式都管用。就拿模式串ABABCABAB来做例子一共9个字符逐项计算子串前j个字符最长公共前后缀长度next[j]含义空串0next[0] -1第一个字符就失配的特殊标记A0next[1] 0第二个字符失配时回退到0AB0next[2] 0ABA1前缀A 后缀Anext[3] 1ABAB2前缀AB 后缀ABnext[4] 2ABABC0next[5] 0ABABCA1next[6] 1ABABCAB2next[7] 2ABABCABA3前缀ABA 后缀ABAnext[8] 3于是ABABCABAB的next数组是index: 0 1 2 3 4 5 6 7 8 next: -1 0 0 1 2 0 1 2 3注意next[3]1的含义当模式串下标为3的字符也就是第4个字符B失配时由于前3个字符ABA的PMT是1j回退到下标1即从模式串的第二个字符B开始继续比较。这张表算明白之后下一步匹配就非常好理解了。你甚至可以自己再造几个例子练手比如模式串AAAA它的next数组推出来是-1, 0, 1, 2, 3这是一个非常好的测试退化场景后面会专门讲。3.3 构建next数组的代码实现与关键细节手算能帮你建立直觉但代码实现才是能跑起来的东西。next数组的构建本质上是用模式串自己匹配自己的过程需要两个指针i指向当前要计算next[i]的后缀末尾位置j指向已匹配前缀的末尾位置。void buildNext(const string p, vectorint next) { int m p.length(); next.resize(m); int j 0; // 当前最长公共前后缀长度 next[0] -1; // 第一个字符失配的特殊标记 int i 1; // 从第二个字符开始计算 while (i m - 1) { // 只计算到m-2最后一个字符的next其实用不到 if (p[i] p[j]) { // 匹配成功公共前后缀长度1 next[i 1] j 1; i; j; } else if (j 0) { // 失配时j回退到自己前一个位置的next j next[j]; } else { // j已经回退到0并且还是失配说明没有公共前后缀 next[i 1] 0; i; } } }这里最让人困惑的是失配分支中j next[j]这一行。它的逻辑和匹配阶段的回退思想完全一致已经匹配的p[0..j-1]这段字符串它内部如果有公共前后缀就能把j回退到较短的前缀上继续尝试而不用从0开始。这是next数组构建O(m)复杂度的关键光是暴力求解公共前后缀就是O(m^3)甚至更高KMP用自匹配的方式把构建过程压到了线性。不过我必须提醒一点上面的循环里i m - 1这个边界条件是按照“只需计算到m-2”来处理的最后一个字符的next值在匹配过程中用不到因为最后一个字符失配时靠的是“匹配好的前m-1个字符”的PMT。这个细节容易写错一旦越界排查起来颇为费劲。更稳妥的写法是直接把循环范围放宽到i m最后生成的next[m-1]保留冗余但不会出错刷题时省心很多。4. 匹配流程与完整代码让KMP真正跑起来4.1 匹配过程逐步拆解next数组到手后匹配阶段就简单了。核心逻辑一句话主串指针i只在匹配成功或首字符失配时前进模式串指针j平时跟着i走失配时按next回退。继续用前面的例子。目标串s是ABABABCABAB模式串p是ABABCnext数组为-1, 0, 0, 1, 2。我逐轮画一下关键过程第1轮i指向s[0]Aj0 ABABABCABAB ABABC s[0]A p[0]As[1]B p[1]Bs[2]A p[2]As[3]B p[3]B 到s[4]A、p[4]C时失配。此时j4查next[4]2。 也就是说前面匹配好的ABAB中最长公共前后缀是ABj回退到2。 第2轮i仍然指向s[4]Aj2 继续比较s[4]A和p[2]A相等 然后s[5]B和p[3]B相等 s[6]C和p[4]C相等 匹配成功模式串起点 i - j 6 - 4 2也就是从s[2]开始匹配。注意第1轮失配后i没有回退还是指向s[4]。这一轮j直接从2开始跳过了模式串的下标0和1因为那两位AB已经被上一轮的匹配结果证明了可以对齐主串的s[2..3]。这就是KMP比暴力匹配高效的原因主串字符被扫描的次数近似为1不存在反复回头比对的情况。如果一直匹配到模式串末尾都没成功就需要在主串中继续寻找下一个可能位置。此时逻辑是匹配完成一次后把j回退到next[j]i继续前进就可以继续寻找下一个匹配点。这个处理方式对“查找所有出现位置”的场景同样适用。4.2 完整代码实现把构建next和匹配两部分拼在一起就是一份最小可用的KMP实现。下面这份我用C写同时额外打印每一次失配时j回退的位置方便跟踪调试。#include iostream #include vector #include string using namespace std; void buildNext(const string p, vectorint next) { int m p.size(); next.resize(m); next[0] -1; int i 1, j 0; while (i m) { if (p[i] p[j]) { next[i] j 1; i; j; } else if (j 0) { j next[j]; } else { next[i] 0; i; } } } int kmpSearch(const string s, const string p) { vectorint next; buildNext(p, next); int n s.size(), m p.size(); int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { // j -1 时走这里会访问 next[-1]吗 // 不会因为分支条件里先判断了 j -1走的是上面那个if cout 失配于主串下标 i j从 j 回退到 next[j] endl; j next[j]; } } if (j m) return i - j; return -1; } int main() { string s ABABABCABAB; string p ABABC; int pos kmpSearch(s, p); cout 匹配位置: pos endl; return 0; }4.3 时间复杂度的直观理解从代码结构可以看出整个匹配过程只有一层while循环i和j的组合变化是单调的主串指针i只会前进模式串指针j虽然会回退但回退的总次数不会超过i前进的总次数。因此匹配阶段是O(n)。构建next数组也是类似结构是O(m)。总时间复杂度O(mn)。对比一下暴力匹配最坏情况O(m×n)当文本量级大、模式串重复度高的时候KMP的优势是几十倍甚至上百倍的。比如在一个100万字符的日志文件里查找一个200字符的敏感词模式暴力在恶劣情况下可能要执行2亿次字符比较KMP大约只需要120万次肉眼可见不是一个量级。4.4 通过手玩示例验证代码调试KMP最有效的办法是自己造例子用代码跑输出再手动画匹配状态核对。我常用的例子有这么几组目标串ababcabcacbab模式串abcac这是一个经典的考研例题next数组是-1,0,0,0,1匹配过程会在第三个字符处经历两次回退。目标串aaaaab模式串aaaab这种重复度高的例子能验证算法不会在相同字符之间无限循环。模式串a目标串aaaaa用于验证边界情况下next数组只有一个-1的表现。空模式串、空目标串检查代码不会越界崩溃。写到这里我必须提一个编码层面的细节上面的代码里j -1是一个很微妙的状态。它表示“模式串第一个字符就和当前主串字符失配”此时正确的做法是主串指针i向前一位、j归零后重新对齐。所以我在if分支里把j -1和“字符相等”放在了一起处理用i; j;把j从-1带到0。这个处理是很多初学者漏掉的一旦忽略用next[-1]就会访问非法内存程序各种奇怪崩溃。5. 进阶变体与常见坑nextval、退化测试与教材差异5.1 next数组的进一步优化nextval先看一个场景。模式串ABABAB目标串ABABAC...前5个字符全都匹配成功第6个字符失配。此时j5查next[5]4于是模式串右移让下标4的字符A去对齐刚才失配的位置。但问题是刚才失配的原因是目标串那个位置的字符不是B而模式串下标4的字符是A也不是B那这一次对齐必然还是失败白白多比较了一次。这种无效回退在模式串存在大量重复前缀时非常常见。解决办法是对next数组再做一次压缩称为nextval数组。构建规则是在求next[i]时如果回退位置next[i]上的字符p[next[i]]与p[i]相同那么nextval[i] nextval[next[i]]否则保持nextval[i] next[i]。用模式串ABABAB推一遍直观感受差异普通next数组-1, 0, 0, 1, 2, 3nextval数组-1, 0, -1, 0, -1, 0可以看到下标2、4、5的nextval值都被压缩了因为回退目标位置的字符和当前字符相同反正也会失配不如直接跳到更早的安全位置。虽然nextval的代码只比next多几行但在对应场景下能减少数次无意义比较我的建议是面试如果时间允许直接上手写nextval版本向面试官展示你对这个优化原理的理解通常印象分不错。5.2 最容易翻车的三个边界坑第一坑next[0]到底该取-1还是0。这个问题在不同教材里答案完全不同。清华版教材的定义习惯是next[0]-1而有些刷题网站或408考纲的写法中next[0]0。不是谁对谁错而是两套体系的索引基准不同。在写代码前先明确自己采用哪套定义然后整套逻辑从头到尾保持一致不要混用。混用的结果就是在循环判断里出现差一错误排查起来极其痛苦。第二坑回退到next[j]之后忘记继续比对当前字符。KMP的匹配循环里失配之后j回退了但下次循环不要直接让i前进而是先拿s[i]去和回退后的p[j]比较。这个顺序一旦搞错就可能漏掉真正能匹配成功的位置。第三坑在构建next的循环里越界。前面说过复用p[i] p[j]判断时j回退到0之后仍然失配的情况要单独分支处理不能让它继续回退。有些人在else分支里忘了处理j 0的情况直接导致死循环或者栈溢出。强烈建议在所有涉及回退的代码里都做一次j边界检查。5.3 与BM算法和暴力搜索的取舍学完KMP之后有人会问那C语言标准库里的strstr用的是KMP吗其实不是。很多主流C库的实现采用的是双向匹配算法Two-Way Algorithm或者简化的BM变体。BM算法的核心思路是“坏字符”和“好后缀”启发式从模式串尾部向前匹配在目标串很长、模式串较短时平均效率往往比KMP表现更好。KMP强在最坏时间复杂度有保证无论数据怎么构造它不会退化到二次复杂度。所以刷题、竞赛、对性能稳定性要求高的嵌入式场景里KMP是首选。而日常办公软件里的查找功能处理的是人类自然语言文本模式串短、重复度低用更简单的算法平均性能也够用。不必迷信KMP是万能的理解不同算法的适用边界同样是算法学习的一部分。5.4 如何设计和用测试例验证自己的实现验证KMP实现是否正确我推荐一套组合拳正确性基础测试目标串abcabcabc模式串abcabc期望结果0首字符失配测试目标串bbbbabc模式串abc期望结果4全匹配测试目标串abc模式串abc期望结果0模式串长于目标串的测试期望结果-1高重复度性能测试构造100万字符的aaaa...aab目标串和20字符的aaa...aab模式串如果代码没有死循环且能在毫秒级返回结果说明没有明显的复杂度退化。我自己第一次写KMP的时候就是在最后一种测试上翻的车。当时next数组构建里少写了一个else分支导致模式串全是A时构建过程陷入反复比较的窘境一次测试直接把程序卡死。后来养成了一个习惯每次写完字符串算法第一件事就是用重复度拉满的极端数据跑一遍确认没有性能悬崖。6. 实战经验与学习路径建议6.1 笔试面试中的手撕诀窍很多人在面试时被要求“10分钟内手写KMP”这个硬性要求其实吓退了不少人但只要把核心逻辑梳理成固定顺序就不怕。我自己的手写顺序是先写buildNext的框架把next[0]-1和三种分支结构列出来再写匹配循环把j -1和p[i]p[j]两组情况合并处理最后补上主串遍历的范围判断和返回值的处理。写完之后不要急着提交先自己举一个3~5字符的小例子在草稿纸上把next数组的值算一遍和代码输出对一下。这个自查动作能拦截掉大部分差一错误。面试官看重的也不全是代码正确性很多时候是看你有没有“调试意识”。6.2 从理解到熟练一条比较顺的学习顺序如果你现在完全不懂KMP建议不要直接从代码开始而是先用前面3.2节“手算next数组”的方式拆解三五个模式串例子把前缀后缀的感觉建立起来。接着写下自己版本的代码哪怕不太优雅只要跑得通就有信心继续优化。然后可以逐步叠加知识点加上nextval优化加入对多模式匹配的思考比如扩展到AC自动机把KMP应用到具体题目里比如重复子串判断、字符串周期问题、求最短循环节。这些题目本质上都是在KMP思想上追加一点变形应用做了几道之后你会有一种“恍然大悟”的通透感。6.3 我实际使用KMP的一点体会工作之后我写过一次KMP场景是处理一批接近千万行的清洗逻辑日志需要把其中命中某类敏感事件的记录全部筛出来。当时模式串有十几种写了个KMP封装作为过滤器跑完一遍之后发现时间比预想中还要快不少对比团队里原来暴力find的旧逻辑整体任务从十几分钟缩短到几十秒。那一刻我对“线性复杂度”这件事才有了具象的感知。但我也要说句实话这个性能提升并不是在所有场景下都这么明显。如果模式串本身只有两三个字符暴力算法直接查反而更快因为KMP光构建next数组的时间就快赶上暴力整个匹配过程了。算法选型永远要考虑常数因子不要只看大O。这也是我踩过几次坑之后总结出来的教训。6.4 最后的实操建议最后分享一个调试KMP时特别管用的小技巧把每次失配时主串指针i、模式串指针j、以及要回退到的next[j]值打印出来和自己在纸上画的推导图一行行对照。绝大多数人理解不了KMP问题就出在“以为自己懂了回退逻辑实际上代码里的j和i变化跟想象对不上”。打印是最直观的纠错方式比自己对着代码空想效率高太多。希望这篇文章能给正在为KMP头疼的人一个相对平滑的切入点。
