1. 在学KMP之前先看清暴力匹配到底慢在哪里1.1 暴力算法最典型的写法和它的浪费点字符串匹配的问题描述起来很简单有一个文本串还有一个模式串要找模式串在文本串中所有出现的位置。换成人话就是拿着一根短针去长布上找洞找出所有针能扎进去的地方。最直觉的写法是一层一层地比int brute_force(char *s, char *p) { int lens strlen(s); int lenp strlen(p); int ans 0; for (int i 0; i lens - lenp; i) { int j; for (j 0; j lenp; j) { if (s[i j] ! p[j]) break; } if (j lenp) { ans; } } return ans; }内层循环一旦遇到不匹配的字符就立刻break然后外层i往前挪一位内层再从模式串的第0个字符开始重新比。代码写起来毫无心理负担但性能隐患就藏在“i往前挪一位”这六个字里。最坏情况什么样文本串是AAAAAAAAAAAAAAAAAAAAB模式串是AAAAAAB前面全是相同的字符只有最后一个字符不一样。每次暴力匹配都是前面6个字符全都比对了到第7个字符才发现不匹配然后外层i只挪一格又重新把前面6个字符逐个比对一遍。假设文本串长度是n模式串长度是m最坏情况下的比较次数是O(n*m)量级。m如果很长这个量级会直接让人崩溃。咱们拿真实数据感受一下文本串1万字符、模式串1000字符最坏情况下暴力算法大概要比较一千万次字节这个量级在普通文本里肉眼已经能感到明显的卡顿。而KMP算法能做到比较次数在O(nm)量级一万个字符几千次比较就结束了差距是两个数量级的问题。1.2 痛感最直接的地方主串指针被强制回退分析暴力匹配的过程最关键的问题不是“比较了多少次”而是“主串指针回退了多少次”。暴力匹配里外层循环变量i最惨它每失败一次就只前进1。注意这个推进不是基于任何有效信息的推进纯粹是因为“当前位置比不了换个位置再试”。根本原因在于模式串失配时我们已经知道文本串这一段有哪些字符但这些已知信息完全没有被利用直接丢了重来。打个比方。你在两排货架上找商品暴力方式是这样的拿着一张购物清单从第1个货架开始比比对到第5个位置发现不对不是我要的东西。然后你做的不是继续看第5个货架后面是什么而是走回第2个货架重新开始比。这显然不符合正常人的购物逻辑——你都走到第5个货架了前面的4个位置怎么排列你已经看得一清二楚完全可以利用这个信息决定下一步还从哪继续看而不是退回去。KMP算法的核心思想就一句话失配时不要退回去重新比利用已经比较过的信息把模式串往后“滑动”到一个合理的、尽量远的位置同时保证不会漏掉潜在的匹配点。1.3 一个具体反例让无用功肉眼可见来看一个经典反例。文本串S ABABABCABABABAB模式串P ABABCABAB。暴力匹配在第0位开始文本前5个字符A B A B A和模式前5个字符A B A B C比对到第4个位置时发生失配——文本是A模式是C。此时暴力算法放弃这轮把起始位置改成1重新开始。但聪明一点的思路立刻就会发现我们刚才已经知道文本串的前4个字符是ABAB。而模式串自己就有个特点它最开头的两个字符是AB最前面的位置以AB打头。那如果从位置1开始重新匹配相当于试图用模式串开头的AB去对齐文本串位置1、2的B A这根本不可能匹配因为在失配前我们已知文本是ABABAB这种交替结构模式串开头是AB那下一个能重新开始匹配的合理起点应该在哪答案是在位置2因为文本串位置2到3是AB正好能对齐模式串开头的AB。暴力算法白白从位置1试了一遍又发现不行再挪到位置2才试到正确方向。一遍一遍试错问题就出在第1步的试错是必然失败的。KMP算法要做的事情就是提前预判这种事把必然失败的尝试直接跳过去。这个预判的数学基础就是模式串自己的前缀和后缀信息——学名叫做“前缀表”而实现它的数组就是我们常说的next数组。2. 前缀表是KMP的灵魂它保存的到底是什么信息2.1 前缀与后缀从字符串内部找“复用价值”先定义两个概念。一个字符串的前缀指的是从开头开始、不包括最后一个字符的任意子串后缀指的是从结尾往前、不包括第一个字符的任意子串。以模式串ABABCABAB为例前缀A、AB、ABA、ABAB、ABABC、ABABCA、ABABCAB、ABABCABA后缀B、AB、BAB、ABAB、CABAB、BCABAB、ABCABAB、BABCABAB现在找出那些既出现在前缀里、也出现在后缀里的字符串它们共同的最长那个就是我们要的东西。AB同时是前缀和后缀ABAB也同时是前缀和后缀。最长的是ABAB长度是4。这个长度数值有什么意义它说的是当我在某个位置发生失配时模式串已经成功匹配过的部分中最前面这一段和后面对应的这一段是相同的结构。既然相同就说明完全不用从头匹配——直接从模式串的第4个字符继续往后比就行。这就是为什么KMP里失配跳转的长度能保存这种“前方信息”。想清楚一个问题为什么最长相等前后缀就能保证“不漏匹配”假设模式串失配时已经匹配成功的那部分是长度为L的前缀如果你知道这个L长度的前缀里最长相等前后缀长度是k那你就可以放心地把模式串向右滑L-k个位置让模式串的前k个字符去对齐文本串已经验证过的后k个字符。因为对齐之后这k个字符已经确定相等了不需要再比。而你滑动的过程中比这更多的偏移动位置有没有可能恰好构成更优的匹配如果存在某个偏移量产生匹配那就意味着除了这k个前缀后缀之外还有更长的相等前后缀这与k是“最长”矛盾。这个简单的矛盾论证就是KMP正确性的根本。2.2 next数组记录长度还是位置别被各种版本绕晕KMP算法面试中被问得最多、也最容易把人绕晕的是next数组的取值规则。市面上的教材里至少有三种定义方式导致很多人背完代码第二天就忘。三种常见定义next[j] 前j个字符组成的子串的最长相等前后缀长度next[j] 前j个字符中最长相等前后缀长度减1然后把-1作为失配的哨兵next[j] 失配时j该跳转到的下标这个下标往往等于最长相等前后缀长度。我推荐直接用第1种定义next[j]就是长度。原因有两个。第一长度最符合直觉推导整个数组的时候你脑子里始终在处理“前缀后缀有多少个字符相等”不需要再做加减法转换。第二当下标从0开始计数时长度为L的前缀结束位置恰好就是下标L失配时让模式串指针j直接跳到next[j]即j next[j]刚好就跳到了最长相等前缀的下一个字符——长度和位置天然统一省去一次加1减1的转换。但魔鬼在细节里。用第1种定义时next[0]怎么处理下标0之前没有字符串最长相等前后缀根本不存在。大多数实现会把next[0]设为-1把它当作“重置”信号当j跳到-1时表示模式串已经完全对齐不上文本串指针必须前进模式串指针回到0。所以next[0] -1不是长度是一个人工哨兵。千万别搞混。next[1]呢模式串前1个字符只有一个字符前缀和后缀都不可能存在所以最长相等前后缀长度是0next[1] 0。这两个初始值记住之后后面的所有值都可以手工推导出来。2.3 词典翻页的直觉已经翻过的页不用重翻KMP的跳转逻辑有一个特别贴切的生活类比你在一本词典里找一个词翻了50页没找到但在这个过程中你记住了第25页到第50页的开头字母都是“Bi”打头。现在要找另一个同样以“Bi”打头的词你自然不会回到第1页而是直接从第25页附近开始。这里的“25页”信息就是已知的前缀信息。更严谨一点说你已经成功匹配了文本串的一整块内容这一整块和模式串的前缀完全一样。现在失配了你要做的事不是扔掉这一整块信息重来而是看看模式串自己的前缀里有没有哪一段能跟这块已匹配内容的末尾结构对应上。有就滑过去没有才彻底重置。这就是很多教程里说的“利用模式串自身的对称性”。注意这个“对称性”不是指回文那种镜像对称而是指前缀和后缀的重叠复用。理解到这一层后面看构建代码就是顺水推舟的事。3. 手算一次next数组完整走一遍构建过程3.1 手工模拟从第一个字符推到最后一个为了确保真懂咱们手工推导一个模式串的完整next数组。就用ABABCABAB长度9。逐步推导过程配合“当前已匹配前缀长度len_p”这个思路i0时没有意义直接next[0] -1。i1时前1个字符是A不存在相等前后缀next[1] 0。i2时前2个字符是AB前缀有A后缀有B不相等next[2] 0。i3时前3个字符是ABA前缀A、后缀A相等长度为1没有更长的了next[3] 1。i4时前4个字符是ABAB前缀AB、后缀AB相等长度2next[4] 2。i5时前5个字符是ABABC前缀ABAB、后缀BABC不相等逐个往前找最长相等前后缀是A前缀A后缀C不对后缀最后一个字符是C前缀A和后缀C不相等单字符也不相等所以next[5] 0。i6时前6个字符是ABABCA前缀A、后缀A相等next[6] 1。i7时前7个字符是ABABCAB前缀AB、后缀AB相等next[7] 2。i8时前8个字符是ABABCABA前缀ABA、后缀ABA相等长度3next[8] 3。i9时前9个字符是ABABCABAB前缀ABAB、后缀ABAB相等长度4next[9] 4。得到next数组[-1, 0, 0, 1, 2, 0, 1, 2, 3, 4]。注意到next下标最大到9比模式串长度多1因为第9个值存的是“整个模式串自己”的前后缀信息。这个多出来的值在“查找所有匹配位置后继续探测”时有特别的用途后面会讲到。手工推导过程看起来很朴素但里面藏了一个规律当求next[i]时往往可以直接利用前一个位置的next值不用把所有前缀后缀都枚举一遍。这就是代码里用双指针递归递推的核心。3.2 构建代码版本选择和关键逻辑基于上面的推导思路给出一个相当简洁的C语言版本这个版本以next[0] -1为起点使用双指针i和j同步推进。void get_next(char *p, int *next) { int m strlen(p); int i 0; // 主推进指针指向当前要求next的下标 int j -1; // 记录“当前最长相等前后缀的长度 - 1” next[0] -1; while (i m) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } }注意这段代码里j的含义和前面手工推导的长度差了一个1j 最长相等长度 - 1。之所以这样写是因为需要把哨兵-1融合进递推逻辑里当j -1时说明没有可以利用的相等前后缀直接进入“开启新起点”模式。这个版本很多教材都有区别只在于有的人维护next时用长度有的人用长度减1要看清楚避免复制代码后逻辑错乱。Python版本更直白一些很多初学者反而觉得Python版更容易理解def get_next(p: str) - list[int]: m len(p) next_arr [-1] * (m 1) i, j 0, -1 while i m: if j -1 or p[i] p[j]: i 1 j 1 next_arr[i] j else: j next_arr[j] return next_arr无论哪种语言版本核心递归逻辑是一致的当p[i]和p[j]相等时意味着当前的前缀和后缀长度都可以扩展1于是长度加1并记录不等时就退回到更短的目前已经计算出的next数组值继续尝试。整个过程可以理解为走在一条自己比自己的“影子”的路上i走在前面j跟在一定距离后它们俩的目标是尽快找出模式串各前缀的对称长度。j回退的路径走的就是前面已经算好的next数组——这也是为什么next数组必须在构造过程中逐步填好。3.3 构建代码里最容易走错的三个分支写这段代码或者抄这段代码的时候有3个点值得停下来多看几眼。第一个点是i变量到底维护到哪。上面代码里while循环条件是i m每次循环体内部i所以循环结束时i会递增到m而next[m]刚好被填写。这也是为什么前面说next数组长度是m1。如果你把next数组申请成m长度那么循环到i m-1时内部next[i1]就会越界这是最常见的崩溃点。第二个点是p[i] p[j]分支里i和j的顺序。为什么先i、j再赋值而不是先赋值再递增因为next数组要记录的是“当前这个前缀结束时新增字符后的新状态”。假设模式串是ABABi走到3、j走到1时p[3]Bp[1]B相等如果不进行i直接让next[3]1那记录的就是还没拼接新字符之前的状态整个递推就全错了。第三个点是失配后j next[j]为什么一定能保证“回退后不会漏”。那是因为next[j]本身就是“当前已匹配前缀的最长相等前后缀长度”相当于从更小的对称结构重新开始尝试。j回退的过程不会跳过合法的解因为它尝试的每一个前缀都是真正出现在模式串头部、同时和当前后缀有重叠的候选这和前面用矛盾法证明的道理是一致的。4. 主匹配流程当失配发生时究竟跳向哪里4.1 KMP匹配主循环代码与执行轨迹next数组构建完成之后真正的匹配部分是简单的甚至可以说简单得让人不敢相信。int kmp_match(char *s, char *p, int *next) { int n strlen(s); int m strlen(p); int i 0; int j 0; int count 0; while (i n) { if (j -1 || s[i] p[j]) { i; j; if (j m) { count; printf(matched at index %d\n, i - m); j next[j]; } } else { j next[j]; } } return count; }这个主循环和暴力匹配最大的不同i几乎从来不回退。总共n次迭代每次要么i前进一格要么j回退后继续尝试。j回退的总次数有限整体复杂度就是O(nm)。真正匹配时逻辑分为三种情况s[i] p[j]两个字符相等文本指针和模式指针都前进s[i] ! p[j] 且 j ! -1失配j跳到next[j]i不动相当于只滑动模式串s[i] ! p[j] 且 j -1模式串已经没法再滑了说明当前位置没有任何可能i前进一格j从0开始。这个执行轨迹有个很有意思的特性失配时不一定要立刻移动i而是反复跳j。比如模式串AAAAAB和文本串AAAAC匹配当i停在“C”时j可能连着跳了好几次每次都是j next[j]直到j跳到-1这时i才前进一格。这种“卡在同一个文本字符上不断调整模式串对齐位置”的行为正是KMP高效的精髓。4.2 匹配成功后为什么要主动跳j而不是直接结束很多初学者第一次写KMP时都会写成一个匹配成功立即返回的模式。但实际应用里我们往往要找出文本串中“所有”出现位置而不仅仅是第一个。这个时候就有个新问题找到一次完整匹配后文本串指针i应该怎么处理还能不能复用已匹配的信息看一个例子文本串ABABABA模式串ABA。第一次匹配成功时结果是下标0到2。如果直接让i i - m 1然后暴力重来那KMP的优势就丢光了。正确做法是匹配成功后把j回退到next[m]——注意这里用的就是前面提到的next数组里“多出来的那个值”也就是整个模式串自身的最长相等前后缀长度。回到模式串ABAB的例子next[4] 2意味着整个模式串的前2个字符AB等于后2个字符AB。当匹配完整个模式串后你其实已经确认了文本串当前段的最后2个字符也是AB那么下一次可能的匹配起点就可以从这2个字符之后开始不需要重新比较。这就是“匹配完成后j next[j]”能继续高效寻找下一个匹配的直接原因。从这里也能看出next数组的最后一个值不是摆设它直接服务于“连续性匹配查找”这个实际需求。4.3 边界条件空模式串、单个字符、全重复字符边界是算法题最容易翻车的地方。先把几个常见又容易出错的场景列一下。模式串为空时理论上没有意义。如果调用者传入空串strlen返回0整个匹配逻辑会退化建议在入口处直接return 0。模式串只有一个字符时next数组只有[-1, 0]两个元素next[m]即next[1] 0。匹配逻辑没有任何异常但要注意匹配成功后j next[j]会回到0也就是说会继续寻找下一个匹配。这个行为面对文本串AAAA和模式串A时会输出4个匹配位置完全正确。全重复字符是最能验证KMP性能的场景但也是next数组最容易让人困惑的场景。以模式串AAAA为例它的next数组是[-1, 0, 1, 2, 3]。注意next[4] 3而不是4因为单个字符构成的前缀长度为4但它的最长相等前后缀长度最多只能是3前缀和后缀不能是整个字符串本身否则就失去了“失配后利用后续信息”的意义。这一点在手工推导时必须刻意留意。还有不少实现会让next数组在重复字符场景下继续压缩优化版下一节专门说。5. 从刷题到应用KMP的进阶构造与真实使用场景5.1 优化版next数组解决“跳了等于没跳”的尴尬前面给的next数组有一个明显不足考察这个反例模式串AAAAB当模式串匹配到最后一个字符B时失配j需要跳到next[4]即3。但p[3]还是A如果文本串那个位置也不是A那跳了一次之后马上还要再跳next[3]即2……一路跳到底相当于连续做了好几次无效跳转。优化思路也很直接在构建next数组时如果p[i] p[next[i]]则让next[i]直接继承next[next[i]]的值跳过那些确定会再次失配的位置。void get_nextval(char *p, int *nextval) { int m strlen(p); int i 0; int j -1; nextval[0] -1; while (i m) { if (j -1 || p[i] p[j]) { i; j; if (p[i] ! p[j]) { nextval[i] j; } else { nextval[i] nextval[j]; } } else { j nextval[j]; } } }代码里多出来的if-else分支就是优化点当新增字符和跳转目标字符相同时直接把之前已经算好的更远跳转值赋给它。这个版本在文本串大量重复字符的场景下能把比较次数进一步压低。不过要说清楚这个数组经常被称为nextval或者优化next它牺牲了数组“原始定义”的一致性换来了匹配时更少的跳转次数实际工程中非常实用。5.2 实际应用编辑器搜索、敏感词过滤、DNA序列查找KMP算法的应用不需要任何花哨魔法。最常见的场景是文本编辑器的“查找”功能。在长文档里搜一个关键词如果编辑器用暴力算法几万字的文档搜一个小短词可能卡顿用KMP后时间开销只是文本长度加模式串长度量级文档再长都感觉不到卡。另一个应用方向是敏感词过滤。系统里维护了一个敏感词列表现在要在用户输入的长文本里把所有出现过的敏感词位置标记出来。由于敏感词经常有重复结构比如ABAB类词KMP天然适合这种重复模式查找。多词匹配一般用AC自动机但AC自动机的前置知识就是KMP理解了单模式匹配再扩展多模式匹配衔接是很平滑的。DNA序列匹配也是KMP的经典应用场景。DNA序列本质上就是一个只包含A、C、G、T四种字符的长字符串生物学上要在一个很长的基因组里寻找某个基因片段的出现位置候选序列可能长达上百万字符。O(n*m)的暴力算法在这种规模下不可接受KMP优势立竿见影。还有一个容易忽视的应用字符串工具库的contains、indexOf、replace等函数的底层实现。很多标准库在特定条件下用BM算法或者双指针优化但对于长度较大的模式串KMP的稳定O(nm)性能是杀手锏。理解KMP后你再去看标准库里那些“奇怪”的匹配代码会有一种豁然开朗的感觉。5.3 常见误区与面试高频追问KMP相关的高频误区有四个我自己也在早期栽过跟头。第一个误区是next数组下标搞混。背诵代码时不清楚next[j]存的是长度还是前一个上下文的哨兵值导致手推时算错。解决方法是牢牢记住“next[j]表示前j个字符的最长相等前后缀长度”这个定义所有分支逻辑从定义出发推一遍。第二个误区是主匹配循环里漏掉j -1这个分支。有些初学者写的失配处理只有j next[j]一条路当j已经跳到-1时还要继续访问p[-1]直接数组越界。而这种越界在短模式下偶尔不会触发等到文本串开头全是重复字符时立刻暴露。第三个误区是匹配成功后i的处理。有人直接把i减回匹配起始位置1重新暴力匹配这就完全违背了KMP“不回头”的设计初衷。正确做法永远是j next[j]用对称信息继续往后找。第四个误区是误以为KMP在所有场景下都比BM算法快。其实在文本串和模式串都较短、且模式串几乎无重复结构时暴力算法的常数很小可能比KMP还快在大文本重复模式结构下KMP才显出碾压优势。工程上要基于数据特征选算法而不是迷信某个特定算法。6. 我的实战体会与建议6.1 掌握KMP的正确姿势别背代码推一遍第一次学KMP的时候我也走了一条弯路对着代码背了两天今天能默写出来明天又忘了。后来真正让我学会的是这样一个动作——拿一支笔在纸上把next数组从0开始一个值一个值地推一遍推出错也不要紧对着代码检查哪里和推导结果不一样然后回头理解为什么代码要这样写。推完一个模式串之后再拿一个全是重复字符的模式串推一遍。你会发现手工推的时候已经能感受到next数组“递减跳转”的过程这种手感比背任何模板都有用。我认为这是最值得分享给算法初学者的经验KMP不是背出来的是自己验算出来的。6.2 一个线上提速的小故事有次处理一批超长文本的检索用最直白的strstr函数底层实现比较激进跑了几十秒改成自写的KMP实现之后同样的数据两秒内跑完。当时最大的感受不是KMP多厉害而是理解了为什么像字符串匹配这种“基础算法”值得花精力去优化——它渗透在太多上层功能里底层省一点上层就能飞起来。那种情况下文本串动辄上百万字符模式串是几千到几万个字符的重复结构完全命中了KMP的优势区间。记住这个前提很重要KMP不是银弹但读懂它的复杂度分析和next数组的构造原理会让你在面临字符串问题时有更清醒的选择依据。6.3 后续可以扩展的方向把KMP吃透之后自然可以往两个方向延伸。一是多模式匹配模式串不再是一个而是几十上百个AC自动机就是KMP的思想在Trie树上的扩展原理是“失配时利用已知前缀自动跳转”。二是二维或更复杂结构上的匹配图像特征匹配、二维矩阵模式查找都会复用KMP这种“预计算跳转表”的思路。最后分享一个小技巧调试KMP代码时打印next数组配合手工推导表对照看是最快的排查手段。不要相信纸上的推导能一次全对代码里常常因为一个边界加一减一就全盘皆错把每步的i、j、next值都打出来比对之后定位错误比盯着代码干看有效得多。这个算法虽然年代久远但它的思想一直作为现代字符串处理的基石存在。只要你还写代码迟早会在某个角落遇到需要高效匹配的场景到那时候愿你今天在next数组上花的时间能帮你少走弯路、少删几行代码。
