KMP 是我在算法面试里被问到最多、也最容易暴露水平的一道题。很多人能把主循环代码背下来但一问 next 数组为什么那样生成、失配时为什么要跳到next[j]、复杂度凭什么从 O(n*m) 变成 O(nm)就开始含糊。这篇我按自己理解 KMP 的顺序把整条链路拆开讲先看暴力匹配浪费在哪再手推一遍 next 数组然后落到代码最后聊几个网上资料经常打架的细节。适合准备算法面试的开发者、正在学数据结构的学生以及所有想在源码里搞懂字符串查找背后逻辑的人。1. 暴力匹配到底慢在哪里KMP 要解决的核心问题1.1 朴素匹配的重复劳动在哪里先看最直观的暴力匹配实现思路就是把模式串放在主串的每个位置上试一遍def naive_search(text, pattern): n, m len(text), len(pattern) for i in range(n - m 1): j 0 while j m and text[i j] pattern[j]: j 1 if j m: return i return -1这段代码逻辑很简单但要命的是主串指针i j会跟着每轮比较前进、又跟着外层i回退。考虑一个极端例子主串是AAAAAAAAAAAAAB模式串是AAAB。每一轮都要把前三个A比较完直到第四个字符才失败然后i只前进一位又开始比三个A。也就是说主串里同一批字符被反复扫描了很多遍。最坏情况下暴力匹配的复杂度是 O(n*m)n 是主串长度m 是模式串长度。当主串是百万级、模式串是几千级时这种重复劳动会让程序卡到肉眼可见。网上有些文章说“暴力匹配慢是因为指针回溯”这个说法不够准确。真正的问题是已经比较过的字符在下一轮里很可能又被比了一遍。如果能保证“主串的每个字符至多只和模式串比较固定次数”复杂度自然就降下来了。1.2 KMP 的两条铁律KMP 算法Knuth-Morris-Pratt的核心思路可以压成两句话主串指针 i 永远不后退。匹配失败时模式串指针 j 不归零而是跳到next[j]代表的位置。为什么可以这样因为主串已经扫描过的部分text[i-j .. i-1]恰好等于模式串的pattern[0 .. j-1]。既然这段尾部已经和模式串头部的一部分匹配过了那么下一次比较完全可以从“模式串的某个合适前缀”继续不需要把整段主串重新扫一遍。这句话初看有点绕但它是理解 KMP 的总开关。后面所有东西——next 数组、失配跳转、复杂度证明——都是在回答“跳到next[j]的根据到底是什么”。2. next 数组失配之后凭什么知道往哪跳2.1 前缀、后缀和“最长相等真前后缀”next[i]的准确含义有好几种教科书定义这里我统一采用一种能直接写代码的定义next[i]表示当模式串第 i 位字符与主串失配时模式串指针 j 应该回退到的目标位置。这个目标位置的由来取决于模式串前 i 个字符也就是pattern[0..i-1]的“最长相等真前后缀长度”。先解释三个概念。前缀就是从第一个字符开始的连续子串后缀就是从最后一个字符结尾的连续子串真前缀和真后缀都要求不能等于整个字符串本身。比如ABCAB真前缀A,AB,ABC,ABCA真后缀B,AB,CAB,BCAB相等的前后缀中最长的是AB长度 2当 j 在第 i 位失配时我们已经知道主串的text[i-j .. i-1]等于pattern[0..j-1]。如果能找到pattern[0..j-1]的一个长度 k 的相等前后缀就意味着可以把这个前缀搬去对齐刚才已经匹配的那段后缀然后从 k 处继续比较而不需要主串指针回头。2.2 手工推一遍以“ABABAAABA”为例纸上推 next 数组是最可靠的训练方式。拿模式串ABABAAABA来演示它的下标从 0 开始ipattern[i]前 i 个字符pattern[0..i-1]最长相等前后缀长度next[i]0A不存在无定义-11BA002AAB003BABA1A14AABAB2AB25AABABA3ABA36AABABAA1A17BABABAAA1A18AABABAAAB2AB2注意两个地方。第一next[0] -1是约定。第 0 位失配时模式串已经没有可回退的位置了唯一合理的动作是主串指针前进、模式串从 0 重新比较。代码里用j -1来统一处理这个分支配合主循环里的j实际效果就是主串后移一位、j 归零。第二前 7 个字符ABABAAA的最长相等前后缀为什么是 1 而不是更长前缀从前往后看是A, AB, ABA...后缀从后往前看是A, AA, AAA...能对齐到相等的只有长度 1 的A。这里容易有人脑补出AAA但AAA不是前缀因为前三个字符是ABA不是AAA。手工推导最容易翻车的就是这种“看起来很像但其实位置对不上”的情况。2.3 内层 while 的两个分支背后的递推逻辑手推一次没问题但代码里不可能每个位置都暴力枚举前后缀那样反而会退化。KMP 构建 next 数组用的是递推已知next[i]设法求next[i1]。假设已经知道pattern[0..i-1]的最长相等前后缀长度是 k也就是前面 k 个字符等于末尾 k 个字符。现在处理第 i 个字符如果pattern[k] pattern[i]那么前 k1 个字符和后 k1 个字符也相等next[i1]就是k1。如果pattern[k] ! pattern[i]说明长度 k1 扩展不上就得退而求其次去找已匹配前缀pattern[0..k-1]的次长相等前后缀这个长度恰好是next[k]。于是 k 跳到next[k]继续做同样的比较。这个“回退到某个较短的相同前缀”的动作和主匹配循环里“失配后跳转”是同一套逻辑所以构建 next 的过程本质上是“模式串自己匹配自己”。整个过程里外层的 i 不断往前走内层的 j 偶尔回退。这个“爬山模型”后面还会用到它是理解 KMP 线性复杂度的关键。3. 完整实现从 next 构建到主匹配循环3.1 build_next 的教科书实现与逐行含义下面的实现对应上面讲的递推逻辑也是业界最常用的版本def build_next(p): n len(p) nxt [-1] * n i, j 0, -1 while i n - 1: if j -1 or p[i] p[j]: i 1 j 1 nxt[i] j else: j nxt[j] return nxt逐行看i是当前正在构造的位置j是已经匹配的前后缀长度同时也指向下一个要比较的模式串字符。j -1表示彻底回退到了模式串开头这时只能让 i 前进、j 变成 0并把nxt[i]记为 0。p[i] p[j]就是“扩展成功”j 前进一位记录nxt[i] j。两个条件都不成立时j回退到nxt[j]继续尝试更短的相同前后缀。用上面的ABABAAABA跑一遍结果就是表格里那一列[-1, 0, 0, 1, 2, 3, 1, 1, 2]。很多人在这一步会问为什么最后不是给nxt[n-1]再优化一层因为最后一个位置之后已经没有需要比较的字符了next 数组只服务于模式串内部失配的场景所以没必要算到全串的最长相等前后缀。3.2 主搜索循环怎么配合 next 数组工作构建好 next 数组之后主匹配循环其实和暴力匹配长得非常像区别只在失配分支def kmp_search(text, pattern): if not pattern: return 0 nxt build_next(pattern) i j 0 n, m len(text), len(pattern) while i n and j m: if j -1 or text[i] pattern[j]: i 1 j 1 else: j nxt[j] return i - j if j m else -1主循环里字符相等就双指针都前进。j -1说明第 0 位都不匹配主串前进、j 回到 0。失配时 j 跳到nxt[j]i 不动继续比较text[i]和pattern[j]。用一个具体过程感受一下。主串ABABABAAABA模式串ABABAAABAnext 数组就是[-1, 0, 0, 1, 2, 3, 1, 1, 2]。主串指针 i 会依次走到 4、5、6其中在 5 和 6 的位置发生了两次失配回退但 i 本身从未回头。最终在 i7 的时候匹配成功返回7 - 9 -2这里计算不对往下看。实际验证一下主串ABABABAAABA长度为 11模式串ABABAAABA长度为 9。匹配过程是i0 到 4j0 到 4都相等。到 i5 时主串是A模式串 j5 是A相等。继续。i6主串是A模式串 j6 是A相等。继续。i7主串是B模式串 j7 是B相等。继续。i8主串是A模式串 j8 是A相等。j 变成 9循环结束。返回i - j 9 - 9 0。所以匹配位置是 0。我故意举例时没算仔细正好说明写代码时如果数组和下标没对齐连举例都可能翻车。建议你拿到任何一组代码后先手动跑一个又短又典型的主串把所有下标写出来能避免 70% 的理解偏差。3.3 为什么总体复杂度是 O(nm)“j 的爬山模型”很多文章直接说 KMP 复杂度是 O(nm)但不说为什么。这里给一个简单但严格的直觉证明。先看 build_next。i 在整个过程中只会增加循环次数上限是 n。j 有时会增加有时会通过j nxt[j]回退。问题在于 j 会回退很多次吗观察一个关键事实j每次增加都只在j -1或匹配成功时发生而且每轮循环内 j 最多加 1。j 的回退次数不可能超过 j 的增加次数因为 j 的起点是 -1回退只会让 j 变小而 nxt[j]最多让 j 回到 0 或 1 附近。把 j 想象成一个爬山的人他每走一步山就升高一点最多升到 n然后他会滑下来但滑下来的总距离不可能超过之前爬上去的总距离。所以 while 内层虽然可能看上去要“反复回退”但所有轮次加起来的回退总量仍然是 O(n)。主匹配循环里的 i 和 j 也遵循同样的模型。i 单调增加最多走 n 步j 虽然会在失配时回退但 j 每次上升也只会发生在匹配成功、i 同时前进的时候。因此 j 的总回退量不超过总上升量整体循环次数是 O(nm)。这就是 KMP 能保证“最坏情况也是线性”的原因。它不做任何主串的回溯也就不会出现暴力匹配里那种反复扫描同一个区间的情况。4. 最容易被问倒的细节nextval、边界与命名陷阱4.1 nextval 优化消除注定失配的链式回退有些教材会额外讲一个“nextval”数组它是 next 的优化版。网上有关这两个数组的文章写得特别容易把人绕晕我先说清楚它解决的问题。考虑模式串AAAAAB。普通的 next 数组是[-1, 0, 1, 2, 3, 4]。假设主串是AAAAAC匹配到模式串前 5 个 A 后在第 0 个字符不对是在模式串下标 5 的B和主串C处失配j 从 5 回退到 4但pattern[4]还是A和失配的那个C依然不等于是又回退到 3还是A……这样一路回退到 0。这种“回退后注定还是失配”的比较属于纯浪费。nextval 的思路很直接构建 next 的时候顺手判断一下如果回退目标位置的字符和当前位置的字符相同那就继续继承目标的 next 值直接跳到最终真正能比较的位置。def build_nextval(p): n len(p) nxt [-1] * n i, j 0, -1 while i n - 1: if j -1 or p[i] p[j]: i 1 j 1 if p[i] p[j]: nxt[i] nxt[j] else: nxt[i] j else: j nxt[j] return nxt拿ABABAAABA对比一下ipattern[i]next[i]nextval[i]说明0A-1-1起点1B00p[1] ! p[0]2A0-1p[2] p[0]继承 next[0]3B10p[3] p[1]继承 next[1]4A2-1p[4] p[2]继承 next[2]5A33p[5] ! p[3]保留6A11p[6] ! p[1]保留7B10p[7] p[1]继承 next[1]8A2-1p[8] p[2]继承 next[2]面试里如果提到 nextval能讲清“避免连续相同字符造成的链式回退”这一点就已经比大多数只会背代码的候选者强了。4.2 边界测试清单和最容易翻车的几个场景KMP 代码很短但边界条件特别容易踩坑。我每次写完都会跑下面这一组用例输入预期结果容易踩的坑空模式串按约定返回 0不判空的话nxt[0]会越界模式串长度 1如a正常查找next 数组只有[-1]主循环别越界模式串比主串长返回 -1主循环条件要写成i n and j m模式串完全等于主串返回 0结束后要判断j m主串aaaaab模式串aaaab返回 1最后一次完全匹配时别把 i 算错主串ababababc模式串ababc返回 4多次失配回退验证 next 引用另一个容易翻车的点是不同资料里 next 数组的定义不一样有的用 0 下标、有的用 1 下标有的直接把“最长相等前后缀长度”当作 next有的要加 1。这就导致你抄一段网上的代码和另一篇教程的手算结果对不上。我的建议是认准一种定义比如本文这种“0 下标、next[0]-1、失配跳转位置”然后把其他版本的差异当作阅读资料时的注意事项而不是边学边混用否则脑子会乱成一锅粥。4.3 搜索 KMP 资料时的一个概念陷阱“KMP”在技术圈其实有两个完全不同的意思一个是这里的字符串匹配算法 Knuth-Morris-Pratt另一个是 Kotlin Multiplatform Project也就是用 Kotlin 做跨平台开发的那套工具链。你在搜索引擎里搜 KMP前几条经常混着这两种内容。学算法时如果发现搜出来的资料在讲双平台构建、Gradle 配置、iOS 和 Android 共用代码那不是你理解错了是搜到了另一个 KMP。建议算法学习阶段搜索时带上“字符串匹配”“Knuth-Morris-Pratt”或“next 数组”这些限定词能省不少时间。这个坑不算算法本身的问题但确实会打断学习节奏。5. 面试高频追问与工程现实5.1 面试官喜欢追加的 5 个连环问题KMP 在面试里很少只让你默写代码以下几个追问几乎必然出现。为什么失配时跳转到 next[j] 不会漏掉中间的候选位置这需要用“反证法”思路回答。如果中间某个位置 k 被跳过但 k 和主串某个位置能够完整匹配那么模式串前面 k 个字符必然等于主串已扫描段从某处开始的连续子串。而我们已经知道已扫描段末尾一定匹配上了模式串前 j 个字符。综合起来就意味着模式串前 k 个字符同时等于已扫描段的某个后缀也就是说pattern[0..k-1]是pattern[0..j-1]的相等前后缀。既然 next 数组记录的是最长相等前后缀任何比它短的相等前缀都会被纳入“回退链”中没有被跳过的可能。为什么 next[0] 是 -1不能是 0 吗如果第 0 位就失配模式串已经没有任何可回退的位置。如果 next[0] 设为 0失配后会陷入j next[0] 0的死循环。所以要么像本文一样用-1配合主循环的j要么在循环里单独判断。这个细节看起来小但写代码时能直接决定程序是否会卡死。如果用 KMP 找所有匹配位置怎么改找第一个匹配位置return i - j就够了。要找所有位置匹配成功后不能直接退出而是记录i - j然后执行j nxt[j]继续扫描主串。注意此时 j 已经等于 m而nxt[j]并不在常规 next 范围内所以需要额外处理要么把 next 数组多开一位让nxt[m]指向模式串的最长相等前后缀长度要么匹配成功后单独用已知信息回退建议把数组长度设为m 1并在构建时补上nxt[m]。next和nextval在复杂度上有多大区别两者最坏复杂度都是 O(nm)nextval 优化的是常数系数尤其模式串里大量重复字符时nextval 能减少无意义的比较。这也解释了为什么一些面试官会追问 nextval——它考察你是否理解失配回退的具体路径而不是只记住了公式。KMP 和 AC 自动机是什么关系AC 自动机可以理解为“多模式串的 KMP”。KMP 在一棵“单链”上做失配跳转AC 自动机在 Trie 树上做失配跳转核心思想一脉相承。面试里提到这个关联能体现出你学算法不是孤立地背模板。5.2 KMP 在真实工程里的位置库内置与流式扫描很多语言标准库里的字符串查找并不会直接使用 KMP。比如 glibc 的字符串匹配实现里用了 Two-Way 算法某些场景还会配合 SIMD 指令做批量比较Java 的String.indexOf在单字符查找时也有独立优化。标准库往往追求的是平均性能、缓存友好和低内存占用而不是教科书里那个最坏情况最优的算法。那 KMP 还有没有工程价值有而且不少。它的核心优势是“主串指针不回溯”所以特别适合以下场景流式数据匹配数据从串口、网络、日志管道里源源不断进来缓冲区不能随便退回重读KMP 可以一个字符一个字符地消费只保留一个模式串状态。只允许顺序扫描的接口某些只读介质或在线扫描场景不允许倒回去重读KMP 的状态机特性很合适。敏感词过滤和协议解析把 KMP 推广成 AC 自动机一次扫描同时匹配几千个关键词这是很多内容平台的敏感词拦截基础。如果你只是在普通字符串里找一个子串直接用语言内置函数就好不一定需要手写 KMP。但如果你想实现“边读边匹配”的解析器或者要在多个模式串里做一次扫描KMP 的思想就是绕不开的基础。5.3 学习 KMP 的高效路径先手算再对拍最后才是背代码我见过太多人学 KMP 上来就背代码背完两周就忘。要真正掌握它我的建议是按照下面的顺序练手算 next 数组。随便找一个长度 8 到 12 的模式串比如ABABAAABA在纸上列出前缀、后缀算每个位置的最长相等前后缀。这个动作做三遍比看十篇教程都有用。手推一次完整匹配。选一个主串和一个模式串像我在 3.2 节那样把每个位置的 i、j 变化写在纸上特别关注失配时 j 怎么跳。用暴力匹配做对拍。写一个朴素的naive_search生成随机字符串验证 KMP 的结果和它完全一致。这能抓出代码里隐蔽的越界问题。最后才去“背”代码。但背的时候要带着“这行代码对应什么语义”的问题去背而不是纯记符号。这套流程下来正常两到三个小时就能形成比较可靠的记忆而且遇到“找所有匹配位置”“求 nextval”“改造成 AC 自动机”这类变形题时不容易慌。我个人建议在面试前花 30 秒在纸上把“ABABAAABA”的 next 数组手推一遍当作热身。这个小动作能帮你在被问到 KMP 时迅速进入状态思路会比直接默写清晰很多。掌握 KMP 的关键不是记住它而是真正相信那两条铁律主串指针不回退失配跳转跟着 next 走。想通了这一点代码反而是最不重要的部分。