这个系列走到第四篇我挑了三块在面试里出场率极高、又经常被混淆的硬骨头Manacher算法、BFPRT算法、KMP算法。题目里标了“上”所以这一篇的主角是KMP——理由是它最基础、最经典同时也是后两个算法思想的前置。Manacher和BFPRT会在下篇里展开讲但这一篇末尾也会先把它们的核心思路交代清楚方便你连着看。先说一个很实际的现象。很多人背KMP代码背得滚瓜烂熟但面试官只要追问一句“next数组是怎么求出来的为什么失配要这么跳”就卡壳了。我面试别人的时候见过太多候选人能把kmpSearch一字不差写出来但next数组手算的每一步却讲不清楚。这就跟你打游戏开局前把大招键位调好了结果团战根本不知道该什么时候按一样代码是背出来的不是理解出来的。所以这篇我会用最笨、最啰嗦的办法把next数组从定义到手算到代码再到优化一条线捋清楚保证你看完不光能默写还能给面试官讲明白它为什么是O(MN)。这篇的定位也很明确正在准备算法面试的候选人、做文本匹配或字符串处理相关业务的开发者以及所有“听说过KMP但从来没真正理解它”的读者。如果说网上那些题解能让你“会用”那我希望你读完这篇能到“能变”的程度——遇到变形题能第一时间想到用KMP的思路去拆。1. KMP算法到底在解决什么问题1.1 先看看朴素匹配有多浪费在聊KMP之前得先知道它替代的是什么。最原始的字符串匹配算法叫BF算法全称Brute Force翻译过来就是暴力匹配。网上很多资料叫它朴素匹配一个意思。它的思路一句话就能讲完主串从每个位置开始依次和模式串的每一个字符比对一旦失配主串指针回退到本轮起始位置的下一个字符模式串指针归零从头再来。用Java写出来大概长这样public static int bfSearch(String s, String p) { int n s.length(); int m p.length(); for (int i 0; i m n; i) { int j 0; while (j m s.charAt(i j) p.charAt(j)) { j; } if (j m) { return i; } } return -1; }这段代码逻辑完全正确但它有一个巨大的浪费每次失配主串指针i都要回退到i1模式串指针j清零把已经比对过的前缀全部重新比一遍。我举个极端但很容易理解的例子主串是aaaaaaab模式串是aaab。前四次匹配全部在最后一个字符上失败每失败一次指针都要回到开头重新来过。也就是说我们明明已经知道主串前面全是a但算法就是“记不住”每次都傻乎乎地重新比较一遍。这个活儿让计算机来干最坏情况下的时间复杂度就是O(N*M)主串长度N模式串长度M每一轮最多比较M次最多可能发生N轮。当N和M都是十万量级时这个计算量就是十亿级别在绝大多数业务场景里已经不可接受了。1.2 KMP把“失败信息”当成了宝贝KMP算法的核心思想其实特别朴素既然我们已经一路比对到了失配位置那就说明这个位置之前的字符全都匹配成功过。这些“已经匹配过的内容”不应该被扔掉而是应该被利用起来。怎么利用用一个例子来说明。假设主串某一段是...ababaX...模式串是ababac我们已经匹配了ababa主串下一位是X模式串下一位是c失配了。此时BF算法会把主串指针退回到这轮开头往后挪一位重新从a开始比。KMP不这么干它知道主串这里刚比对完的内容就是ababa那么在这段内容的后缀里有没有可能同时也是模式串的前缀答案是有的ababa的后缀aba恰好是模式串的前缀aba。既然这样这3位已经确认相等就不需要重新比了直接把模式串挪到后缀对齐前缀的位置继续往后比就行。这就是KMP最核心的洞察匹配失败时不是从头再来而是利用已匹配部分的前后缀重叠让模式串跳到一个更聪明的位置。这个“跳多少”的信息需要预先算好存在一个数组里这个数组就叫next数组。而主串指针则永远不回退一直是往前走的。这样整个匹配过程就变成了主串的一次扫描而不是暴力匹配那种“来回反复横跳”。一句话总结KMP不是不回溯而是让模式串的指针跳到一个更聪明的、绝对安全的位置主串指针则永远不回退。这是整个算法最核心、最反直觉、也最值得反复琢磨的点。1.3 这三个算法为什么值得放在一讲里顺便交代一下系列安排。Manacher算法解决的是最长回文子串问题BFPRT算法解决的是无序数组第K小TopK问题KMP解决的是字符串匹配问题。表面看三个问题毫不相干但它们的底层思维方式惊人地一致都是通过预处理信息或者精心构造的划分避免重复计算把暴力方法的最坏复杂度打下来。KMP是其中思想门槛最低、应用覆盖面最广的一个所以安排在“上”。你如果把KMP的next数组彻底理解了再去看Manacher的回文半径数组会发现结构上有很多相似的地方都是预处理一张表然后在扫描时查表跳跃。这也是我坚持先讲KMP的原因它是后面那些漂亮算法的“热身操”。2. next数组KMP的灵魂2.1 先对齐定义不然代码越看越乱在进入手算之前我必须先花一段篇幅统一定义。因为next数组不同资料里有不同写法有人从0开始计数有人从-1开始有人存“最长相等前后缀长度”有人直接存“失配后应该跳到的下标”。这些版本都不错但如果你同时看了两份不同门派的资料很容易越看越晕代码也会因为混用版本而出bug。我在这篇里采用的版本是工程界最常见的写法next[i]表示模式串p[0..i]这个子串的“最长相等前后缀长度”且这个长度不能等于整个子串的长度也就是不能拿自己跟自己比较。定义约定next[0] 0因为单个字符没有真前缀也没有真后缀最长相等前后缀长度为0。在匹配阶段如果模式串的指针在j位置失配那么模式串指针跳到next[j-1]。注意最后一条的j-1这是很多初学者第一眼会卡住的地方。原因是失配发生在模式串的第j个字符下标j意味着我们前面已经确认了p[0..j-1]这j个字符是匹配成功的。所以能用来找“最长相等前后缀”的是p[0..j-1]这个子串也就是next[j-1]。市面上另一套常见写法是next[i]直接存失配时应该跳到的位置也就是next[i]已经做过减一处理失配时直接j next[j]。那套写法核心思想完全一样只是表里的值往前错了一位。千万别两套混着看否则代码和手算结果总是差1会非常折磨人。2.2 手算next数组以模式串“abacaba”为例手算是理解KMP的必经之路。我拿一个面试里经常出现、且非常适合演示的模式串abacaba来算一遍。先给出核心原则构建next[i]的过程本质就是在求p[0..i]这个子串的最长相等前后缀长度。我们从头开始逐步推导每一步都看一次。i字符当前子串比较过程next[i]0aa单字符没有真前后缀01babp[1]b 与 p[0]a 比较不相等j保持002aabap[2]a 与 p[0]a 相等j变为113cabac先与p[1]b比较不相等回退到next[0]0再与p[0]a比较不相等04aabacap[4]a 与 p[0]a 相等j变为115babacabp[5]b 与 p[1]b 相等j变为226aabacabap[6]a 与 p[2]a 相等j变为33最终得到next [0, 0, 1, 0, 1, 2, 3]。这个结果建议你自己在纸上推一遍别看我在表格里写得轻松实际很多人在第3步就会卡壳。我自己当年学的时候恰恰是卡在这里。为什么第3步会是难点因为当比较到p[3]c时前面已经出现过长度为1的相等前后缀子串aba中前缀a等于后缀a所以现在j1我们尝试着把前后缀长度从1扩展到2拿p[1]b和p[3]c比较结果不相等扩展失败。关键来了接下来怎么办不是回到j0重新开始而是看“已经匹配好的那个前缀本身”有没有更短的前后缀重叠。p[0..0]就是a它的next[0]0所以j从1回退到0。然后再拿p[0]a和p[3]c比还是不等此时j已经等于0无法再回退于是next[3]0。这中间那句“看已经匹配好的前缀的next值”其实就是KMP里最难绕过的弯——构建next数组的过程本质上就是拿模式串匹配模式串自己失配时的回退逻辑和正式匹配时的回退逻辑一模一样。我第一次想通这个点的时候有种“原来如此”的顿悟感。2.3 构建next数组的代码实现理解了手算流程代码就好写了。下面是Java版本的构建逻辑public static int[] getNext(String p) { int m p.length(); int[] next new int[m]; next[0] 0; int j 0; for (int i 1; i m; i) { while (j 0 p.charAt(i) ! p.charAt(j)) { j next[j - 1]; } if (p.charAt(i) p.charAt(j)) { j; } next[i] j; } return next; }代码非常短但每一行都有讲究。j在这里表示“当前已经匹配成功的前后缀长度”也是“下一个要拿来比较的前缀位置”。一开始j0从i1开始扫描模式串。每到一个新位置先看当前字符p[i]能不能扩展已有的相等前后缀也就是和p[j]是否相等。如果相等j然后把j写入next[i]。如果不相等就进入while循环回退j。这个while循环里写的j next[j-1]和我们手算时遇到失配的回退方式完全一致。为什么能保证不会漏掉可能的匹配因为next[j-1]已经是p[0..j-1]这个子串的最长相等前后缀长度了回退到那里等于把模式串的前缀“平移”到已经匹配上的后缀位置这是所有可能重叠方案里跳得最远又不会跳过头的一个。还有一点值得注意整个构建过程的时间复杂度是O(m)。虽然内层有一个while循环看起来可能退化但实际上j每通过if分支增加1最多只会因为回退而减少若干次而j增加的次数总共不超过m次。回退不会凭空增加它是把之前增加的那些次数“消耗”掉。所以整体均摊下来是严格的O(m)这也是KMP能保持线性时间的底气。2.4 next数组的改进版本nextvalnext数组已经是能用的版本但它有一个小的性能瑕疵。举个例子模式串是aaaa它的next [0, 1, 2, 3]。假设匹配时主串是aaab模式串在最后一个字符处失配p[3]a 匹配不上主串的 b按之前的规则j会先跳到next[2]2但p[2]还是a和失配位置字符一样必然再次失配于是又跳到next[1]1还是a仍然失配最后跳到next[0]0才发现p[0]也是a还是失配。这一串跳转都是无用功。于是就有了nextval优化构建next数组时如果发现p[i] p[next[i]]那就直接把nextval[i]设置为nextval[next[i]]的取值相当于把“因为字符相同导致的必然失配”提前跳过。对于aaaa这个例子优化后nextval [0, 0, 0, 0]失配时一步就直接跳到底省掉了中间的无意义比较。从复杂度角度看这个优化并不改变KMP的O(MN)上界只是把常数项压得更低。面试时能说出这个优化说明你是真的理解失配的本质了而不是单纯背代码。不过要注意nextval的代码写起来比next数组略微绕建议先把基础版吃透再上这个优化不要一上来就混着学。3. KMP匹配流程与完整代码实战3.1 匹配主流程拆开看有了next数组匹配阶段反而简单了。直接上完整实现public static int kmpSearch(String s, String p) { int n s.length(); int m p.length(); if (m 0) { return 0; } int[] next getNext(p); int j 0; for (int i 0; i n; i) { while (j 0 s.charAt(i) ! p.charAt(j)) { j next[j - 1]; } if (s.charAt(i) p.charAt(j)) { j; } if (j m) { return i - m 1; } } return -1; }主流程里最重要的一个事实是主串指针i从头到尾只走了一遍无论匹配是否失败i都不会回退。这跟BF算法里i反复回退形成了鲜明对比。j在失配时通过next[j-1]跳转可能变小但它不会影响主串的扫描进度。这里要额外强调两个边界处理。第一模式串为空时直接返回0不然p.charAt(0)就会抛越界异常这种边界问题在面试时特别容易挂。第二标准KMP返回的是模式串第一次出现的起始下标如果没有匹配返回-1。很多人会在j m时直接返回i结果差了一个模式串长度这种低级错误在被面试官盯着写代码时特别容易犯。3.2 手把手模拟一遍完整匹配纸上谈兵没意思我们拿一个具体例子模拟完整过程。主串ababacababab模式串ababab。先算模式串的next数组next [0, 0, 1, 2, 3, 4]这个大家可以自己验算一遍。匹配过程如下i0时s[0]ap[0]a相等j变成1。i1s[1]bp[1]b相等j变成2。i2s[2]ap[2]a相等j变成3。i3s[3]bp[3]b相等j变成4。i4s[4]ap[4]a相等j变成5。i5时s[5]cp[5]b不相等。此时j5失配看next[4]3j跳到3。继续在同一轮i5比较s[5]c与p[3]b不相等j跳到next[2]1。再比s[5]c与p[1]b不相等j跳到next[0]0。继续比s[5]c与p[0]a不相等j保持0。i6s[6]ap[0]a相等j变成1。i7s[7]bp[1]b相等j变成2。i8s[8]ap[2]a相等j变成3。i9s[9]bp[3]b相等j变成4。i10s[10]ap[4]a相等j变成5。i11s[11]bp[5]b相等j变成6此时j等于模式串长度返回11 - 6 1 6。整个过程里主串指针i从0走到11一次都没回头但模式串指针j在i5那一轮里连续跳了三次5→3→1→0。这三次跳跃就是KMP省时间的本质它把“不可能匹配成功的位置”全部跳过而不是傻傻地从头比较。你在面试手写这段逻辑时把“为什么跳到这里不会漏掉答案”解释清楚面试官基本就会觉得你是真懂了。3.3 时间复杂度分析O(MN)是怎么来的KMP最著名的结论就是时间复杂度为O(MN)很多资料直接把这个结论甩出来但从不解释为什么。实际这个分析并不难关键在于“均摊”两个字。主串指针i从0遍历到N-1每个字符最多被比较一次这个比较次数撑死N次所以主串部分的代价是O(N)。接下来看模式串指针j。它有两种变化一是匹配成功时j二是失配时回退变小。j这个操作在整个匹配过程中最多发生M次因为j一旦达到M就匹配成功了整个过程结束它不可能无限增长。而回退操作每次都会让j变小回退的总次数不可能超过之前增长的总次数否则j就变负数了所以所有回退加起来也是O(M)。两部分一加总代价就是O(NM)。这个论证思路特别像“你手里最多攒了多少钱就最多能花掉多少钱”。很多人纠结while循环会不会导致某个字符被反复比较很多次答案是不会因为每次因为失配进入whilej都会减少而j的“存款”是有限的。面试时把这个道理讲清楚比背一个结论要有说服力得多。和BF算法做个直观对比对比项BF算法KMP算法最坏时间复杂度O(N*M)O(NM)空间复杂度O(1)O(M)主串指针失配后回退永不回退模式串指针失配后清零按next数组跳转适用范围模式串极短或要求极简实现模式串长、重复匹配多、性能敏感3.4 KMP在算法面试里的经典应用字符串匹配本身是最直接的应用但next数组的价值远不止于此。我总结几个高频变形题每一个都能看到KMP思想的影子。第一类查找首次出现位置。比如LeetCode 28原题名叫实现strStr()后来改成了findIndex本质上就是裸KMP。这种题练的就是你能不能把模板写对、边界处理好。第二类判断字符串是否由重复子串构成。LeetCode 459就是这类题。比如abcabcabc就是由abc重复三次构成的。这里有个非常漂亮的结论设字符串长度为n它的next值为next[n-1]如果n % (n - next[n-1]) 0那么这个字符串就一定可以由某个子串重复构成且最小周期就是n - next[n-1]。拿abcabcabc验证一下n9最长相等前后缀是abcabc长度为69 % (9-6) 0成立最小周期3答案就是abc。这个结论很多资料会直接给但你想过为什么吗其实道理很简单整个串的最长相等前后缀重叠的偏移量就是最小周期而这个偏移量正好等于n - next[n-1]。第三类最短回文串。LeetCode 214给定aacecaaa要求在前面添加最少字符让它变成回文。做法是把原串反转构造s # reverse(s)然后求这个拼接串的next数组最后一个位置的next值就是原串最长的前缀回文长度。剩下补几个字符就一目了然了。这里面的巧妙点在于用#作为分隔符避免前缀跨越原串和后缀串产生错误匹配。这种构造拼接串再用KMP求前缀后缀重叠的技巧在很多字符串题里都特别好用。第四类AC自动机。多模式串匹配的经典算法它的fail指针本质上就是KMP的next数组在Trie树上的扩展。理解了KMP的失配跳转再去看AC自动机的fail指针你会发现思路完全是一脉相承的。所以KMP不只是解决一道题它是一整套字符串处理思维方式的地基。4. 手写KMP最容易踩的坑和排查方法4.1 边界一next数组下标越界写KMP最容易出的bug就是数组越界尤其是next[j-1]这一句。当j0时j-1是-1直接取next[-1]必然崩。所以while循环里j 0这个条件不能省它不是优化是保命。我见过很多人背代码时把while条件写成while (s.charAt(i) ! p.charAt(j))少了j 0结果跑测试用例时七八个直接越界面试当场社死。4.2 边界二模式串为空和模式串比主串长模式串为空时按惯例返回0。这个用例看起来无关紧要但很多候选人在现场写的时候压根没考虑被测试用例打脸后赶紧补特别影响印象分。另外如果模式串长度m大于主串长度n直接返回-1其实更稳妥虽然标准KMP也能跑但没必要浪费那一次无谓的扫描。4.3 经典失误把两套next定义混着用前面说过next数组有“存最长相等前后缀长度”和“存失配跳转位置”两套门派。混着用的症状非常典型手算出来的next数组和代码跑起来的结果对不上或者代码在主串与模式串完全匹配时返回的下标总是差1。排查这类问题第一件事就是确认你手算时用的定义和代码里的取法是否一致。我自己的习惯是始终用next[j-1]这套因为它对应最长相等前后缀长度的定义手算的时候思路最直接。4.4 排查技巧用暴力对拍验证正确性写完KMP不验证等于白写。但怎么验证效率最高我最推荐的方法是对拍。具体做法很简单写一个正确但慢的BF朴素匹配版再写一个KMP版然后用随机生成的主串和模式串反复测试断言两个版本返回的结果完全一致。一旦不一致立刻缩小范围定位。public static void test() { String chars ab; Random random new Random(); for (int t 0; t 100000; t) { int n random.nextInt(50); int m random.nextInt(20); StringBuilder sb1 new StringBuilder(); StringBuilder sb2 new StringBuilder(); for (int i 0; i n; i) { sb1.append(chars.charAt(random.nextInt(chars.length()))); } for (int i 0; i m; i) { sb2.append(chars.charAt(random.nextInt(chars.length()))); } String s sb1.toString(); String p sb2.toString(); int expected bfSearch(s, p); int actual kmpSearch(s, p); if (expected ! actual) { System.out.println(Mismatch: s s , p p); break; } } }对拍脚本是我从搞竞赛那会儿就开始用的方法后来做工程验证也一直在用。它最大的好处是覆盖了手写用例很难想到的边界组合比如模式串短到1个字符、主串全是相同字符、模式串完全不存在等。KMP这种逻辑容易写错细节的算法用对拍跑几万次随机数据基本能把隐藏bug全部逼出来。5. 下篇预告Manacher算法与BFPRT算法5.1 Manacher算法O(N)求最长回文子串回文子串问题在字符串题里出镜率极高。暴力解法是枚举每个中点向两边扩展时间复杂度O(N^2)遇到长字符串就扛不住了。Manacher算法的思路则巧妙得多它有两个核心点。第一通过插入特殊分隔符把奇数和偶数长度的回文串统一处理。例如原串aba变成#a#b#a#原串abba变成#a#b#b#a#处理后每个回文串都变成了奇数长度可以直接用统一的方式计算。第二维护一个当前最右回文右边界R和它的回文中心C。扫描时如果当前遍历到的位置i在R的左侧那么可以利用对称性直接参考i关于C的对称点i的回文半径。这个操作让每个位置的扩展次数被严格控制最终整体时间复杂度降到O(N)。它和KMP有个相似之处都是通过预处理信息避免重复比较。KMP用next数组记录前后缀重叠长度Manacher用回文半径数组记录已计算过的对称区域。理解了KMP的“查表跳跃”再来看Manacher的“对称半径复制”会轻松很多。5.2 BFPRT算法最坏O(N)求第K小无序数组中找第K小元素最朴素的思路是排序时间复杂度O(NlogN)。快排的partition思路可以把期望降到O(N)但最坏情况比如pivot每次都选到最大或最小会退化到O(N^2)。BFPRT算法也叫中位数的中位数算法专门解决这个最坏退化问题。它的核心动作是精心选择pivot先把数组每5个元素分成一组每组排序后取中位数接着递归地对这些中位数集合求中位数得到pivot。然后按照快排partition的方式把数组分成小于等于pivot和大于pivot两部分再根据K落在哪个区间递归处理。为什么选5个一组因为这个分组方式在数学上能保证以选出的pivot划分后两个子问题中较大的那个规模最多是原数组的7/10。于是递归复杂度T(N)T(N/5)T(7N/10)O(N)用主定理或递归树展开都能证明整体是O(N)。选其他常数也可以但5是证明比较方便、实际效果也比较均衡的阈值。下篇我会把这个证明过程完整写出来并给一份可运行的Java实现。5.3 三个算法背后的共性思维KMP、Manacher、BFPRT表面上是三个割裂的经典算法但它们的精髓其实是同一条方法论想尽一切办法利用已知信息跳过那些不可能成功的尝试。KMP利用的是已匹配部分的前后缀重叠Manacher利用的是回文的对称性BFPRT利用的是精心构造的划分保证。这也是算法面试里最能拉开差距的地方。面试官不指望你背下所有题解但期待你能在遇到新问题时往这个方向去思考这道题的已知信息里有没有什么结构是我还没利用上的所以下篇我不会只丢代码而是会把每个算法的设计动机、证明过程和手推细节都摊开讲重点还是大家最需要的“为什么这样做”的思考过程。我个人刷了这么多题之后的真实体会是KMP、Manacher、BFPRT这三个算法几乎是“背了忘、忘了再背”的循环里最典型的一批。第一次看不懂next数组太正常了我当年也是花了两个晚上盯着那张手写推导表才突然想通“构建next的过程就是模式串自己匹配自己”这句话。建议你拿到这篇之后第一遍跟着手撸next数组的推导第二遍合上文章把代码默写出来第三遍用对拍脚本自己验证一遍这三步走完基本就忘不掉了。Manacher和BFPRT我们下篇见。