说实话KMP本身不难难的是next数组。我第一次学KMP的时候教程里又是“递推公式”又是“回退指针”看完一头雾水。代码倒是能背下来可换个字符串就完全不会用每次刷题遇到字符串匹配只能老老实实暴力匹配心里又憋屈又无奈。后来花了很长时间把数学符号全扔掉只盯着字符串本身看才真正明白next数组到底在干什么。这篇就用最笨的图解方式把next数组从头到尾掰开揉碎讲清楚全程不出现任何数学公式适合刚接触KMP、或者背过模板但从没真正理解过next数组的同学。1. 暴力匹配到底慢在哪先看清问题的本质很多讲KMP的文章上来就甩next数组读者还没弄明白为什么要救这个“进度条”自然看得云里雾里。所以我们先退一步看看暴力匹配到底把时间浪费在哪里。假设主串是ABABABCABABAC模式串是ABABAC。暴力匹配的思路非常简单把模式串从主串的每个位置对齐然后逐字符比较比到失败就把模式串整体右移一位再从头开始比。这个过程里最气人的是你明明已经辛辛苦苦比对了前面五个字符ABABA结果最后一个字符对不上暴力法把前面五个字符的信息全部扔掉然后只把模式串往右挪了一格重新开始比较。这相当于你辛辛苦苦搭了一栋房子的地基发现顶楼缺了一块砖你的解决方案是把地基拆了换个地方重新盖。我们来具体看一下浪费在哪里。当模式串在主串下标0处对齐时比较过程是这样的主串: A B A B A B C A B A B A C 模式串: A B A B A C ↑ 当前位置第五个字符 B 对不上模式串的 C此时我们已经确认了模式串的前5个字符ABABA和主串的对应位置完全一致。暴力匹配会怎么做模式串右移一位从主串下标1开始重新比较主串: A B A B A B C A B A B A C 模式串: A B A B A C请看模式串的第一个字符是A主串下标1是B直接失败。这次比较是必然失败的因为上一次匹配时我们已经知道下标1是B模式串第一个字符是A根本不可能匹配成功。暴力匹配的愚蠢之处就在这里它不记得自己已经看过的字符。每次右移一位都要重新去比较那些已经被验证过“不可能匹配成功”的位置。随着主串越来越长这种“重复劳动”会越来越多整体耗时接近两个字符串长度的乘积数据量一大就肉眼可见地卡顿。那么换一个思路上一次匹配虽然失败了但我们知道了“模式串的前5个字符和主串某一段完全相等”这个信息。这个信息能不能保留下来让模式串一次性多跳几位答案是能。这正是KMP算法的出发点。而帮助KMP做出“正确的跳跃距离”的东西就是next数组。2. 前缀与后缀理解next数组唯一需要的东西在接触next数组之前只需要搞懂两个概念前缀和后缀。不需要任何数学功底就是字面意思。一个字符串的前缀指的是去掉最后一个字符后从开头开始的所有子串。比如字符串ABA前缀有A、AB注意ABA本身不算前缀因为前缀必须不包含最后一个字符一个字符串的后缀指的是去掉第一个字符后从结尾开始的所有子串。还是ABA后缀有A、BA注意ABA本身也不算后缀那什么叫做“公共前后缀”很简单就是一个字符串的某个前缀恰好和它的某个后缀一模一样。我们最关心的是最长的公共前后缀因为它记录了当前这段字符串里头部和尾部最大程度重合的部分。比如字符串ABABA前缀A、AB、ABA、ABAB后缀A、BA、ABA、BABA仔细观察A既在前缀列表里又出现在后缀列表里ABA也是其中最长的公共前后缀是ABA长度为3再比如字符串AAAA前缀A、AA、AAA后缀A、AA、AAA最长公共前后缀是AAA长度为3这里有一个很容易踩的误区很多人本能地以为AAAA的公共前后缀是AAAA长度4。这不对因为前缀不能包含最后一个字符后缀不能包含第一个字符字符串本身永远不会算作自己的前缀或后缀。理解这一点之后看下面的内容就会顺畅很多。用一句话概括next数组里存的就是“模式串从开头到当前位置这一整段子串”的最长公共前后缀长度。下标i对应的值代表模式串前i1个字符组成的子串它的头部和尾部最大能重合多长。3. 手工推导next数组从一个具体模式串说起光看定义还是有点虚我们直接拿模式串ABABAC来手推一遍。先介绍一下背景后面所有讨论中next数组都采用“长度版”即next[i]存储的就是p[0..i]这个子串的最长公共前后缀长度。例如next[4]就是ABABA的最长公共前后缀长度3。我们一步一步来。下标 i子串 p[0..i]该子串的公共前后缀最长公共前后缀长度next[i]0A空001AB无002ABAA113ABABAB224ABABAA、ABA335ABABAC无00这张表是怎么来的以i4也就是子串ABABA为例它的前缀是A, AB, ABA, ABAB后缀是A, BA, ABA, BABA两边都出现且最长的是ABA长度3所以next[4]3。再看i5整个模式串是ABABAC前缀有A, AB, ABA, ABAB, ABABA后缀有C, AC, BAC, ABAC, BABAC完全没有任何重合所以next[5]0。这个推导过程虽然直观但效率太低。想象一下模式串有1000个字符你每算一个next[i]都要暴力枚举一遍所有前缀和后缀整体工作量比暴力匹配还要夸张。我们来看KMP是怎么利用已经算好的结果快速推出下一个值的。4. 递推的真正难点失配时为什么要回退到next[j-1]这是整个KMP算法里最劝退的一步也是很多教程含糊带过的地方。我把它拆开来讲。求next数组时我们不是从头为每个子串重新枚举前缀后缀而是一路递推过去。沿用上面的ABABAC用一个变量j来记录“当前已经搭好的公共前后缀长度”。注意这里的j同时也可以当作“模式串下一个待比较字符的下标”这一点非常关键。初始状态next[0] 0j 0因为单个字符没有公共前后缀。计算next[1]子串AB拿新字符p[1]B去和p[j]p[0]A比较不一样而且j已经是0无法再减少所以next[1]0j保持0。计算next[2]子串ABA新字符p[2]A和p[0]A一样说明公共前后缀长度从0变成1j加1为1所以next[2]1。计算next[3]子串ABAB新字符p[3]B和p[1]B一样j从1变成2所以next[3]2。计算next[4]子串ABABA新字符p[4]A和p[2]A一样j从2变成3所以next[4]3。到这里都比较顺每次比较p[i]和p[j]相等就j加1然后next[i]j。但轮到i5的时候好戏来了。当前j3意思是“已经确认模式串前5个字符ABABA的公共前后缀长度是3”也就是ABA在头部和尾部重合了3个字符。现在要看新字符p[5]C能不能把这个重合继续延长就要比较p[j]p[3]B和p[5]C。结果不一样。怎么办不是把j直接清零重来而是回退到next[j-1]。为什么是next[j-1]而不是next[j]也不是0我们先看这个过程j当前是3说明p[0..2]和p[2..4]是重合的。但现在p[3]B接不上p[5]C所以长度为3的公共前后缀方案失败了。我们要找一个更短的、仍然成立的前后缀。怎么找注意当前已经确认p[0..2]ABA和p[2..4]ABA一样。我们要在“现有重合”的基础上缩小范围就得看看ABA自己内部有没有更短的前后缀。而ABA的最长公共前后缀长度正好是next[2]1。所以把j从3收缩到next[2]1然后再次比较p[j]p[1]B和p[5]C。这里有一个绝大部分教程不会点破的关键回退到next[j-1]本质上是在“已重合的那段子串”里寻找更短的有效重合。你可以把已经搭好的长度为3的重合想象成一座桥桥塌了但桥的两端还各有一段地基也就是A这两段地基仍然可以作为新的更短的重合继续使用。而next[j-1]告诉你的恰恰就是这段地基的长度。好回到例子。j收缩到1后比较p[1]B和p[5]C仍然不一样。那就继续收缩j收缩到next[j-1]next[0]0。此时j0比较p[0]A和p[5]C还是不一样而且j已经到0了没法再收缩于是next[5]0。完整的图解是这样的模式串: A B A B A C 下标: 0 1 2 3 4 5 推 next[5] 时j 3 已重叠的是: A B A A B A 尝试扩展: B vs C 失败 收缩 j next[2] 1 新重叠是: A A 尝试扩展: B vs C 失败 收缩 j next[0] 0 尝试扩展: A vs C 失败 j 已到 0无法再收缩 next[5] 0回退到next[j-1]的物理意义是p[0..j-1]这段已经确认相等的字符串它的最长公共前后缀可以继续借用因为这段字符串的尾部现在正和主串或模式串已处理的部分对齐我们直接把模式串的头移动到它自己的尾部位置跳过那些注定匹配不了的比较。如果你还是觉得绕想一个生活化的场景一辆火车进站车头撞上了障碍物但后面十几节车厢已经稳稳地贴在站台上。你要重新发车不可能把火车完全倒回起点而是看看车头和出站口之间有没有可能直接衔接。next数组就是告诉司机“你的车头退到第几个轮子正好可以接着往前开。”这一段是整个KMP的核心值得多看几遍。一旦理解了回退原理上面那段求next数组的代码就变成顺理成章的事了。vectorint buildNext(const string p) { int n p.size(); vectorint next(n, 0); int j 0; // j 表示当前已匹配的公共前后缀长度 for (int i 1; i n; i) { // 不匹配就收缩用前面已经算好的 next 来定位 while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; }注意代码里while循环的条件j 0才允许收缩否则j一直是0就会陷入死循环。这个边界条件很多人第一次写都会漏掉后面我们会专门讲踩坑。5. 用next数组做匹配完整示例演示一遍求出了next数组接下来看看它怎么在匹配的时候发挥作用。还是用前面的例子主串S ABABABCABABAC模式串P ABABAC此时已经求好的next数组是next [0, 0, 1, 2, 3, 0]匹配过程我们一步一步走并用图展示每一次跳跃的原因。第一步模式串在主串下标0处开始对齐一路比较到i5, j5主串: A B A B A B C A B A B A C 模式串: A B A B A C ↑ 主串这里是 B模式串这里是 C失配此时失配的是模式串第5个字符C下标5。注意已经匹配成功的部分是p[0..4]ABABA。按照next数组next[4]3意思是ABABA的头尾有长度为3的重合ABA。所以我们把模式串右移让这个重合部分继续对齐j从5变成3主串: A B A B A B C A B A B A C 模式串: A B A B A C ↑ 继续从这里比较主串 i5 是 B模式串 j3 也是 B匹配这一步就是KMP比暴力匹配强的地方其他暴力做法此时只敢右移一位然后从模式串头重新开始比而KMP直接右移两位还保留了三位已经确认相等的字符少做了三次注定失败的比较。匹配继续i6, j4时又出问题主串第6个字符是C模式串第4个字符是A失配。此时已匹配部分是p[0..3]ABAB查next[3]2于是j从4收缩到2主串: A B A B A B C A B A B A C 模式串: A B A B A C ↑ 主串这里是 C模式串 j2 是 A还是失配继续收缩。现在j2已匹配部分是p[0..1]AB查next[1]0于是j从2收缩到0主串: A B A B A B C A B A B A C 模式串: A B A B A C ↑ 主串这里是 C模式串 j0 是 A仍失配此时j0且字符不匹配模式串已经没有可收缩空间只能让主串前进一位i从6变成7主串: A B A B A B C A B A B A C 模式串: A B A B A C ↑从图中可以看到模式串的起始对齐位置被反复“甩”到后面但每一次甩动都是基于已经确认的信息不会漏掉任何一个可能匹配成功的位置。接下来的过程一路顺畅i7 j0 A A i8 j1 B B i9 j2 A A i10 j3 B B i11 j4 A A i12 j5 C C主串下标7到12这六位正好是ABABAC匹配成功起始位置是13 - 6 7。把整个匹配过程整理成一张表看起来会更直观主串下标 i模式串下标 j比较结果动作依据0~40~4全匹配一路前进-55B vs C 失配j 收缩到3next[4]353B vs B 匹配i, j-64C vs A 失配j 收缩到2next[3]262C vs A 失配j 收缩到0next[1]060C vs A 失配ij 已为07~120~5全匹配成功-这个例子完整展示了next数组的两种用途一是让模式串“大步跳跃”二是当大步也失败时还能“逐级收缩”而不是一次性清空回到起点。KMP之所以比暴力快正是因为它在失配时永远不丢掉已经得到的信息。6. 落地代码两种写法、边界与踩坑记录原理搞清楚了代码就不难写了。我在前面给出了构建next数组的长度版代码这里把匹配函数也补全顺便聊几个我实际踩过的坑。完整的C示例#include iostream #include vector #include string using namespace std; vectorint buildNext(const string p) { int n p.size(); vectorint next(n, 0); int j 0; for (int i 1; i n; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; } int kmpSearch(const string s, const string p) { if (p.empty()) return 0; vectorint next buildNext(p); int i 0, j 0; int n s.size(), m p.size(); while (i n j m) { if (s[i] p[j]) { i; j; } else if (j 0) { j next[j - 1]; } else { i; } } return (j m) ? i - j : -1; }这里有一个非常容易出错的点next[j - 1] 和 next[j] 的区别。网上很多代码写的是j next[j]看得人一头雾水。其实那是另一种“偏移版”的定义它把next数组的含义从“最长公共前后缀长度”改成了“失配时跳回的下标”两者差了一个位置。学的时候只认准一种定义代码全部围绕一种定义来写就不会混。Python版本也顺手贴一下语法更瘦一些def build_next(p): n len(p) nxt [0] * n j 0 for i in range(1, n): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt def kmp_search(s, p): if not p: return 0 nxt build_next(p) i j 0 while i len(s) and j len(p): if s[i] p[j]: i 1 j 1 elif j 0: j nxt[j - 1] else: i 1 return i - j if j len(p) else -1盘点一下几个我写KMP时踩过的坑第一个坑是while判空/死循环。求next的时候j 0这个条件必须写在前面否则j next[j - 1]在j 0时会访问next[-1]直接越界或者死循环。我见过的最典型错误是有人把while写成while (p[i] ! p[j])然后问为什么程序卡住不动——因为当第一位就对不上时j永远不会变成正数。第二个坑是返回位置算错。匹配成功后正确的起始位置是i - j。因为匹配完成后i指向主串中模式串结尾的下一个位置j等于模式串长度减掉正好是匹配起始位置。有些人会写成i - m或者i - j 1一两个特殊样例能过稍微变一变就错了。第三个坑是空模式串。KMP匹配函数通常在模式串为空时需要返回0但构建next数组时n 0会直接返回空数组匹配函数里如果没做空串判断可能在while循环里直接跳过并错误地返回 -1。加一行保护代码最省心。第四个坑也是大家最常遇到的问题不同教程里的next数组长得不一样。我整理了一个简易换算关系避免你被别的资料搞晕版本数组形态以ABABAC为例代码里回退写法长度版本文使用[0, 0, 1, 2, 3, 0]j next[j - 1]偏移版[-1, -1, 0, 1, 2, -1]j next[j]失配跳转版[-1, 0, 0, 1, 2, 3]j next[j]看到这里你应该明白了不是网上代码错了而是大家约定的定义不同。用一种定义学透再看其他版本时要先搞清楚它说的是什么千万别逐字照搬。7. 回退次数有没有上限为什么KMP足够快知道next数组怎么用之后还有一个很多人关心的问题KMP到底快在哪里它的回退动作那么多真的比暴力快吗先看主串指针i。在整个匹配过程中i只有一条路不断向右移动。它永远不会因为失配而退回去重新比较。这意味着主串里的每一个字符在最坏情况下也只被比较一次。再看模式串指针j。它确实会来回跳匹配成功时增加失配时通过next数组收缩。但请注意j的每次增加都伴随着主串指针i的前进。而j的每次减少其实是在“消耗”之前已经积攒起来的匹配长度。你可以把j想成一个反复使用但总量有限的资源它一共增长了多少、最多也就能回退多少。这样一解释结论就很直观整个匹配过程里主串走了一趟模式串的来回跳跃总次数也不会超过主串长度太多。整体耗时跟两个字符串的总长度大致成正比而不是暴力的“长度相乘”。这也是为什么大家都说KMP是线性时间算法——不需要数学公式只从指针的移动规律就能感受到它的高效。从刚才的完整示例也能看到主串的每个字符最多被比较两次一次在j较大时被对比一次在j收缩到0时再次对比。某些教程里会把复杂度写成看起来很吓人的式子但本质就是这么一回事指针不回头信息不丢失。8. nextval优化与学习建议比next数组更进一步最后说一个很容易被人忽略的优化变体nextval数组。它解决的是next数组在某些特殊场景下的“无效回退”问题。举个例子模式串是AAAAAB。它的next数组是[0, 1, 2, 3, 4, 0]。如果用这个next数组去匹配主串当模式串第5位B前面的A失配时j会从4一路收缩到3、2、1、0每一次收缩之后要比较的字符仍然是A而失配的字符也是A所以这些比较注定是失败的。显然连续回退四次都在做无用功。nextval的思路是在构建next数组时如果计算出来的回退位置j所指向的字符和当前位置i的字符一样那就没有必要回退到j而是直接继承next[j]的值跳过一个无效比较。说白了就是“一步能退到位就不要分四步慢慢退”。代码上nextval其实只在next的基础上加了一步判断vectorint buildNextval(const string p) { int n p.size(); vectorint next(n, 0); int j 0; for (int i 1; i n; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } // 优化如果回退后的字符和当前字符相同继续沿用更早的next值 if (i 1 n p[i 1] p[j]) { next[i] next[j]; } else { next[i] j; } } return next; }注意这个写法里我处理的是i1位置的字符因为它本质上是为“下一个字符失配时该跳到哪”服务的。这个优化对一般字符串来说提升不一定明显但在连续重复字符很多的情况下能省下大量无效比较。对你而言我的建议是先把本篇文章的next数组彻底吃透再去研究nextval。next数组是地基地基不稳谈优化只会让代码变成一团乱麻。学完原理之后最好拿纸笔在草稿纸上照着ABABAC这种模式串手动演算一遍再把代码敲一遍最后把代码里的next数组打印出来和你手算的表格对照一下。只要这一步能对上KMP在你的脑子里就再也跑不掉了。