1. 为什么我要花一整个周末把 KMP 算法彻底拆开字符串匹配这件事看起来简单到不值一提——不就是在一段文本里找一个词吗很多语言的标准库一行代码就搞定了。但如果你真的动手写过底层文本处理工具或者被面试官按在椅子上追问过“next 数组到底怎么求”你就会明白KMP 这个算法是那种“看一遍觉得懂了合上书自己写就废了”的典型代表。我最早接触 KMP 是在做一个日志分析的小工具时。当时需要从几百万行日志里快速定位特定的错误模式用最朴素的暴力匹配跑一遍要好几秒换成 KMP 之后直接降到了几百毫秒。那个性能差距让我第一次真正意识到字符串匹配的效率核心不在于你多快能比较字符而在于你能多聪明地跳过那些根本不可能匹配的位置。这篇内容就是把我这些年反复理解 KMP、给别人讲 KMP、以及在实际项目里用 KMP 的经验一次性整理清楚。我会从最朴素的暴力匹配讲起一步步推导出 KMP 的核心思想把 next 数组的求法掰开揉碎最后再聊 KMP 的优化版本。不管你是正在准备面试的开发者还是想真正搞懂这个算法的工程师跟着走一遍应该能彻底拿下它。提示这篇内容假设你会至少一门编程语言能看懂基本的数组操作和循环。不需要你有任何算法竞赛背景我会尽量用大白话把每个环节讲透。2. 从暴力匹配说起KMP 到底在解决什么问题2.1 暴力匹配的思路和它的致命缺陷先来看最直观的字符串匹配方式。假设我们有一个主串也叫文本串和一个模式串要在主串里找到模式串第一次出现的位置。暴力匹配的做法非常直接从主串的第一个字符开始逐个和模式串的字符比较。如果全部匹配成功就返回当前位置如果中途某个字符不匹配就把模式串整体往右移动一位从主串的下一个位置重新开始比较。用代码表示大概是这样def brute_force_search(text, pattern): n len(text) m 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这段代码逻辑上没有任何问题但它的时间复杂度是 O(n × m)其中 n 是主串长度m 是模式串长度。在最坏情况下比如主串是 “aaaaaaaab”模式串是 “aaab”每一次比较都要比到模式串的最后一个字符才发现不匹配然后主串指针回退重新再来。我当初做日志分析的时候日志行平均长度在 200 个字符左右模式串大概 20 个字符。暴力匹配在单行上看起来很快但几百万行累积下来加上最坏情况的回退耗时就很可观了。2.2 KMP 的核心洞察主串指针不回退KMP 算法由三位计算机科学家在 1977 年共同提出它的核心洞察其实只有一句话当匹配失败时我们已经知道了主串中前面那些字符是什么不需要把主串的指针回退只需要移动模式串即可。这句话听起来简单但它是整个 KMP 的灵魂。让我用一个具体例子来说明。假设主串是 “abababc”模式串是 “ababc”。我们用两个指针 i 和 j 分别指向主串和模式串当前比较的位置。前四个字符 “abab” 都匹配成功i 和 j 都走到了各自字符串的第五个位置。此时 text[4] ‘a’pattern[4] ‘c’不匹配。如果是暴力匹配我们会把 i 回退到 1j 归零重新开始比较。但 KMP 说等等我们已经知道了 text[0..3] “abab”而模式串的前四个字符也是 “abab”。在这个已匹配的前缀 “abab” 中有一个很重要的性质——它的前缀 “ab” 和后缀 “ab” 是相同的。这意味着什么意味着模式串中开头的 “ab” 已经和主串中位置 2 到 3 的 “ab” 对齐了。我们完全不需要回退主串指针只需要把模式串向右滑动让模式串的前缀 “ab” 对准主串中已经匹配过的后缀 “ab”然后从主串的第五个字符继续比较。这就是 KMP 的精髓利用已经匹配过的信息避免主串指针的回退。主串指针 i 永远只往前走时间复杂度从 O(n × m) 降到了 O(n m)。2.3 为什么暴力匹配会做无用功理解 KMP 的关键是要理解暴力匹配到底在哪些地方做了无用功。还是上面的例子。暴力匹配在 i0 失败后会把 i 移到 1然后比较 text[1] 和 pattern[0]。但我们在第一轮比较中已经知道了 text[1] ‘b’而 pattern[0] ‘a’这两个字符根本不可能匹配。这一轮比较完全是浪费。更一般地说暴力匹配在每一轮失败后都丢弃了之前所有已匹配的信息从零开始。而 KMP 把这些信息保存下来通过一个叫做 next 数组也叫前缀函数、失配函数的东西告诉我们在失配时应该把模式串滑动到哪里。注意很多人学 KMP 的时候卡在 next 数组上觉得这个东西像是从天上掉下来的。其实 next 数组记录的就是模式串自身的“自匹配”信息——每个位置之前的前缀和后缀有多长的重合。理解了这一点next 数组就不再神秘了。3. next 数组KMP 最核心也最容易搞混的部分3.1 next 数组到底记录了什么next 数组是 KMP 算法的核心数据结构。对于模式串的每一个位置 jnext[j] 表示的是模式串的前 j 个字符组成的子串中最长的相同前缀和后缀的长度。我知道这个定义读起来很绕让我用例子来解释。假设模式串是 “ababc”。我们逐个位置来看对于 j0也就是空前缀next[0] 通常定义为 -1这是一个约定后面会解释为什么。对于 j1子串是 “a”它没有真前缀和真后缀真前缀是指不包含最后一个字符的前缀真后缀是指不包含第一个字符的后缀所以 next[1] 0。对于 j2子串是 “ab”前缀有 “a”后缀有 “b”没有相同的所以 next[2] 0。对于 j3子串是 “aba”前缀有 “a”、“ab”后缀有 “a”、“ba”。其中 “a” 和 “a” 相同长度是 1所以 next[3] 1。对于 j4子串是 “abab”前缀有 “a”、“ab”、“aba”后缀有 “b”、“ab”、“bab”。最长的相同前后缀是 “ab”长度是 2所以 next[4] 2。所以对于 “ababc”next 数组是 [-1, 0, 0, 1, 2]。这个数组的物理意义是当模式串在第 j 个位置失配时我们应该把模式串滑动到 next[j] 的位置继续比较。换句话说模式串的前 next[j] 个字符已经和主串中当前位置之前的 next[j] 个字符匹配上了不需要重新比较。3.2 手工推导 next 数组的完整过程理解了 next 数组的含义之后我们来看怎么手工求它。这个过程是面试中经常被要求手写的所以值得反复练习。以模式串 “ababaca” 为例我们逐个位置推导位置 j子串最长相同前后缀next[j]0空无-11a无02ab无03aba“a”14abab“ab”25ababa“aba”36ababac无0所以 next 数组是 [-1, 0, 0, 1, 2, 3, 0]。手工推导的时候有一个小技巧对于位置 j你只需要看前 j 个字符组成的子串找出最长的那个“既是前缀又是后缀”的字符串。注意这里的前缀和后缀都不能是子串本身必须是真前缀和真后缀。我当初练习的时候经常犯的一个错误是把整个子串也算进去。比如对于 “aba”如果允许前缀等于子串本身那最长相同前后缀就是 “aba”长度是 3但这显然不对。记住必须是真前缀和真后缀。3.3 用代码递推求解 next 数组手工推导适合理解概念但实际写代码的时候我们需要一个高效的递推方法来求 next 数组。这个递推过程本身就是 KMP 思想的体现。递推的核心思路是假设我们已经知道了 next[0] 到 next[j-1] 的值现在要求 next[j]。我们看 pattern[j-1] 和 pattern[next[j-1]] 是否相等如果相等那么 next[j] next[j-1] 1。如果不等就令 k next[j-1]然后继续比较 pattern[j-1] 和 pattern[k]直到找到相等的或者 k 变成 -1。这个过程的代码实现如下def build_next(pattern): m len(pattern) next_arr [0] * m next_arr[0] -1 if m 1: next_arr[1] 0 j 2 k 0 # k 表示当前最长相同前后缀的长度 while j m: if pattern[j - 1] pattern[k]: k 1 next_arr[j] k j 1 elif k 0: k next_arr[k] else: next_arr[j] 0 j 1 return next_arr这段代码看起来不长但里面的 k next_arr[k] 这一行是很多人卡住的地方。它的含义是当 pattern[j-1] 和 pattern[k] 不相等时我们需要找一个更短的相同前后缀。而 next_arr[k] 正好记录了 pattern[0..k-1] 这个子串的最长相同前后缀长度所以我们直接跳到那里继续比较。提示如果你在面试中被要求手写 next 数组的求解建议先用一个小例子比如 “ababaca”在纸上走一遍确认自己理解了每一步 k 的变化然后再写代码。直接背代码很容易在细节上出错。4. KMP 匹配过程把 next 数组用起来4.1 匹配流程的完整拆解有了 next 数组之后KMP 的匹配过程就相对直观了。我们用两个指针 i 和 j 分别遍历主串和模式串如果 text[i] pattern[j]则 i 和 j 同时加一。如果 j 走到了模式串末尾说明匹配成功返回 i - j。如果 text[i] ! pattern[j]则根据 j 的值处理如果 j 0令 j next[j]i 不变。如果 j 0令 i 加一。用代码表示def kmp_search(text, pattern): n len(text) m len(pattern) if m 0: return 0 next_arr build_next(pattern) i 0 j 0 while i n: if text[i] pattern[j]: i 1 j 1 if j m: return i - j elif j 0: j next_arr[j] else: i 1 return -1注意这里 next 数组的定义和前面手工推导的略有不同。在这段代码中next[j] 表示的是当模式串在第 j 个位置失配时应该跳转到的位置。对于 “ababc”这个版本的 next 数组是 [-1, 0, 0, 1, 2]和前面手工推导的结果一致。4.2 用具体例子走一遍匹配过程让我用主串 “ababababc” 和模式串 “ababc” 来完整走一遍匹配过程。next 数组是 [-1, 0, 0, 1, 2]。初始状态i0j0。text[0]‘a’pattern[0]‘a’匹配i1j1。text[1]‘b’pattern[1]‘b’匹配i2j2。text[2]‘a’pattern[2]‘a’匹配i3j3。text[3]‘b’pattern[3]‘b’匹配i4j4。text[4]‘a’pattern[4]‘c’不匹配。j4 0所以 j next[4] 2。text[4]‘a’pattern[2]‘a’匹配i5j3。text[5]‘b’pattern[3]‘b’匹配i6j4。text[6]‘a’pattern[4]‘c’不匹配。j4 0所以 j next[4] 2。text[6]‘a’pattern[2]‘a’匹配i7j3。text[7]‘b’pattern[3]‘b’匹配i8j4。text[8]‘c’pattern[4]‘c’匹配i9j5。j m匹配成功返回 i - j 9 - 5 4。所以模式串 “ababc” 在主串 “ababababc” 中第一次出现的位置是 4。你可以看到整个过程中主串指针 i 从来没有回退过一直是递增的。这就是 KMP 高效的根本原因。4.3 时间复杂度分析KMP 的时间复杂度是 O(n m)其中 n 是主串长度m 是模式串长度。为什么因为主串指针 i 从 0 走到 n每次循环要么 i 加一要么 j 减小。而 j 最多增加到 m所以 j 减小的总次数不会超过 m。因此整个匹配过程的循环次数是 O(n m)。构建 next 数组的过程也是 O(m)因为 j 从 2 走到 mk 的变化也是单调的。对比暴力匹配的 O(n × m)KMP 在处理长文本和长模式串时优势非常明显。我当初做日志分析的时候主串长度是几百万模式串长度是几十KMP 比暴力匹配快了将近两个数量级。5. KMP 的优化从 next 数组到 nextval 数组5.1 原始 KMP 的一个小缺陷标准的 KMP 算法已经很快了但在某些特殊情况下它还会做一些不必要的比较。考虑模式串 “aaaab” 和主串 “aaabaaaab”。next 数组是 [-1, 0, 1, 2, 3]。当 i3j3 时text[3]‘b’pattern[3]‘a’不匹配。根据 next 数组j next[3] 2。然后比较 text[3]‘b’ 和 pattern[2]‘a’仍然不匹配。j next[2] 1。再比较 text[3]‘b’ 和 pattern[1]‘a’还是不匹配。j next[1] 0。最后比较 text[3]‘b’ 和 pattern[0]‘a’不匹配。j 已经是 0i 加一。你会发现因为模式串的前四个字符都是 ‘a’当 text[3]‘b’ 和 pattern[3]‘a’ 不匹配时它必然也不会和 pattern[2]、pattern[1]、pattern[0] 匹配。这三次额外的比较完全是浪费。5.2 nextval 数组的改进思路优化的思路很直接如果 pattern[j] 和 pattern[next[j]] 相等那么当 pattern[j] 失配时pattern[next[j]] 也一定失配我们可以直接跳到 next[next[j]]。基于这个思路我们可以在构建 next 数组的时候顺便做一步优化得到 nextval 数组。对于模式串 “aaaab”nextval[0] -1。对于 j1pattern[1]‘a’next[1]0pattern[0]‘a’两者相等所以 nextval[1] nextval[0] -1。对于 j2pattern[2]‘a’next[2]1pattern[1]‘a’两者相等所以 nextval[2] nextval[1] -1。对于 j3pattern[3]‘a’next[3]2pattern[2]‘a’两者相等所以 nextval[3] nextval[2] -1。对于 j4pattern[4]‘b’next[4]3pattern[3]‘a’两者不等所以 nextval[4] next[4] 3。所以 nextval 数组是 [-1, -1, -1, -1, 3]。用 nextval 数组重新走一遍匹配过程当 text[3]‘b’ 和 pattern[3]‘a’ 不匹配时j 直接跳到 nextval[3] -1然后 i 加一。原本需要四次比较现在一次就跳过了。5.3 nextval 的代码实现def build_nextval(pattern): m len(pattern) nextval [0] * m nextval[0] -1 if m 1: nextval[1] 0 j 2 k 0 while j m: if pattern[j - 1] pattern[k]: k 1 if pattern[j] ! pattern[k]: nextval[j] k else: nextval[j] nextval[k] j 1 elif k 0: k nextval[k] else: nextval[j] 0 j 1 return nextval这段代码和构建 next 数组的代码非常相似唯一的区别在于当 pattern[j-1] pattern[k] 时多了一步判断如果 pattern[j] 和 pattern[k] 相等就继承 nextval[k] 的值否则才用 k。注意nextval 数组的优化在模式串中有大量连续重复字符时效果最明显。对于一般的模式串优化幅度可能不大。但在实际工程中这种优化几乎不增加额外成本所以能用就用。6. 实际项目中的 KMP从理论到落地6.1 什么时候该用 KMPKMP 虽然高效但并不是所有字符串匹配场景都需要它。我个人的经验是如果主串和模式串都很短比如都在几十个字符以内暴力匹配完全够用代码还更简单。如果主串很长几万字符以上或者需要反复匹配比如在一个大文本里找多个模式串KMP 的优势就体现出来了。如果模式串本身有大量重复的前后缀比如 “abababab”KMP 的优化效果尤其明显。在实际项目中很多语言的标准库已经内置了高效的字符串匹配算法。比如 Python 的 str.find() 底层用的是改进的 Boyer-Moore 算法Java 的 String.indexOf() 在短字符串时用暴力匹配长字符串时用 KMP 的变体。所以如果你只是调用标准库不需要自己实现 KMP。但如果你在做底层开发或者需要定制化的匹配逻辑比如带通配符的匹配、多模式串匹配理解 KMP 就非常重要了。6.2 一个实际案例日志模式匹配回到我最初提到的日志分析工具。当时的场景是从几百万行日志中找出所有包含特定错误模式的行。日志行的格式大概是这样的2024-01-15 10:23:45 ERROR [main] com.example.Service - Connection timeout after 30000ms我需要匹配的模式是 “Connection timeout after”后面跟一个数字然后是 “ms”。如果用暴力匹配每行日志平均 150 个字符模式串 25 个字符最坏情况下每行要比较 150 × 25 3750 次。一百万行就是 37.5 亿次比较耗时大约 3-4 秒。换成 KMP 之后每行最多比较 150 25 175 次一百万行是 1.75 亿次比较耗时降到了 200 毫秒左右。这个提升在需要实时分析日志的场景下非常关键。6.3 多模式串匹配的扩展思路KMP 只能处理单个模式串的匹配。如果需要在同一段文本中同时匹配多个模式串可以考虑 Aho-Corasick 算法它本质上是 KMP 在多模式串上的扩展——把多个模式串构建成一棵 Trie 树然后在 Trie 树上构建类似 next 数组的失配指针。我在另一个项目里用过 Aho-Corasick 来做敏感词过滤原理和 KMP 一脉相承。如果你理解了 KMP 的 next 数组理解 Aho-Corasick 的失配指针就不会太困难。7. 常见问题与排查技巧实录7.1 next 数组求解时的常见错误我在教别人 KMP 的时候发现大家最容易在以下几个地方出错错误一next[0] 的初始值搞混。有的教材把 next[0] 定义为 0有的定义为 -1。这两种定义方式对应的匹配代码不同。如果你混用了就会出现数组越界或者死循环。我的建议是选定一种定义方式从头到尾保持一致。我个人习惯用 -1因为这样在匹配代码里处理 j0 的情况更自然。错误二递推时 k 的回退逻辑写错。在构建 next 数组的递推过程中当 pattern[j-1] ! pattern[k] 时需要令 k next[k]。很多人会写成 k next[j-1] 或者 k k - 1这都是不对的。k next[k] 的含义是在 pattern[0..k-1] 这个子串中找更短的相同前后缀。错误三忘记处理模式串长度为 1 的情况。如果模式串只有一个字符next 数组的构建和匹配过程都需要特殊处理。很多模板代码在这个边界条件下会出错。7.2 匹配过程中的死循环问题KMP 匹配过程中最常见的 bug 是死循环。通常是因为在 j0 且不匹配时忘记让 i 加一。# 错误写法 while i n: if text[i] pattern[j]: i 1 j 1 elif j 0: j next_arr[j] # 缺少 else: i 1如果 j0 且 text[i] ! pattern[0]上面的代码会一直循环因为 i 和 j 都没有变化。正确的写法必须加上 else 分支让 i 前进。7.3 性能调优的实操建议如果你在实际项目中使用 KMP以下几个调优建议可能对你有帮助优化点具体做法预期效果使用 nextval 替代 next构建时多一步判断减少重复字符的比较次数预分配数组提前分配好 next 数组的内存避免动态扩容的开销使用字符数组而非字符串在 C/C 中将字符串转为 char 数组避免每次索引时的边界检查批量处理对多行文本一次性构建 next 数组减少重复构建的开销提示在 Python 中字符串索引本身就有一定的开销。如果对性能要求极高可以考虑用 bytes 类型或者 array 模块来存储字符序列。7.4 面试中的高频追问如果你在面试中被问到 KMP除了基本的算法流程面试官还可能追问以下几个问题为什么 KMP 的时间复杂度是 O(nm)关键在于主串指针不回退以及 j 的回退总次数不超过 m。next 数组和 nextval 数组的区别是什么nextval 在 next 的基础上跳过了那些必然失配的位置。KMP 和 BM 算法有什么区别BM 算法从模式串的末尾开始比较利用坏字符规则和好后缀规则在实际应用中通常比 KMP 更快但实现也更复杂。能不能用 KMP 做多模式串匹配可以扩展到 Aho-Corasick 算法核心思想是在 Trie 树上构建失配指针。8. 我踩过的坑和最后分享的几个小技巧第一次自己实现 KMP 的时候我在 next 数组的递推上卡了整整一个下午。代码看起来和教材上一模一样但跑出来的结果就是不对。后来我拿了一个特别简单的例子——“aabaaab”——在纸上一步一步走才发现问题出在 k 的回退上。我当时写的是 k next[j-1]而正确的写法是 k next[k]。这两个看起来很像但含义完全不同。后来我养成了一个习惯每次实现 KMP 之后先用几个边界用例测试——模式串长度为 1、模式串和主串完全相同、模式串比主串长、模式串在末尾才匹配成功。这几个用例能覆盖绝大多数边界 bug。另外一个小技巧是如果你在面试中一时想不起 next 数组的递推公式可以先写出暴力匹配的代码然后尝试手动优化。面试官通常更看重你的思考过程而不是你能不能背出代码。最后KMP 这个算法值得反复咀嚼。每过一段时间重新看一遍你可能都会有新的理解。它不仅仅是一个字符串匹配算法更是一种“利用已知信息避免重复计算”的思维方式。这种思维方式在很多其他算法和工程问题中都能派上用场。