KMP算法详解：从暴力匹配到线性时间字符串匹配

1. 每日算法题 11一道字符串匹配题背后的 KMP 原理先说一下这个系列的背景。每天安排一道算法题不是为了刷数量而是把零散的知识点串成体系。第 11 期我选了字符串匹配这个方向因为字符串相关的问题在实际业务里出现频率非常高——从日志检索、关键词过滤到基因序列比对本质都是在做模式串匹配。今天的题目是给定文本串 T 和模式串 P找出 P 在 T 中首次出现的位置如果不存在则返回 -1。很多朋友第一反应是暴力匹配从 T 的每个位置开始逐个字符和 P 比较失败就后移一位。这个思路没有错但最坏情况下的时间复杂度是 O(n*m)当文本串是几百万字符、模式串又长又有大量重复前缀时性能完全扛不住。所以这题的核心考点就是 KMP 算法它能把匹配过程优化到 O(nm)线性时间复杂度这也是面试里极其高频的算法知识点。本期我就围绕这道题把 KMP 的前因后果、next 数组的推导、代码实现和容易踩的坑一次讲透。2. 暴力匹配为什么不行先看清问题本质2.1 一次失败的匹配里有多少信息被浪费了假设文本串 T abacababacab模式串 P abacaba。暴力匹配的做法是从 T[0] 开始逐位比较 P[0..6]比较到 T[6] 时发现字符不匹配于是把模式串整体右移一位再从 P[0] 重新开始比较。这样做的问题在于前一轮已经匹配成功的 6 个字符信息在右移一位之后完全被丢弃了下一轮又从零开始比较。举个更直观的例子。模式串 P abacaba前面 6 个字符 abacab 已经匹配上了第 7 个字符失配。此时其实可以观察到abacab 有着明显的前后缀重复结构——前缀 ab 和后缀 ab 是相同的。这意味着模式串右移时不必只移动一位而是可以直接跳到让前缀和后缀对齐的位置省掉中间大量无效的比较。暴力匹配浪费的正是这部分可预判的信息。2.2 KMP 的核心思想让模式串自己记住该跳到哪KMP 算法做了一个很朴素但很聪明的改变在匹配之前先对模式串做一次预处理算出一个 next 数组。next[i] 的含义是当 P[i] 失配时i 应该回退到哪个位置继续比较。这里的回退依据是 P[0..i-1] 中最长的相等前后缀长度。这样在匹配过程中文本串的指针永远不需要回退只有模式串的指针在失配时按 next 数组跳转。整体复杂度从暴力法的 O(n*m) 降到了 O(nm)因为每个字符最多被比较两次——一次匹配成功一次失配跳转。理解这个思想比记住代码重要得多因为凡是涉及到重复前缀匹配的场景这个思路都能复用。3. 动手推导 next 数组以 P abacaba 为例3.1 前缀和后缀的定义要抠清楚在计算 next 数组之前必须先明确什么是字符串的前缀和后缀。一个字符串的前缀是去掉最后一个字符后剩下的任意头部子串后缀是去掉第一个字符后剩下的任意尾部子串。以 abacab 为例它的前缀集合包括 a、ab、aba、abac、abaca后缀集合包括 b、ab、cab、acab、bacab。这里 ab 既是前缀也是后缀长度为 2。所谓最长相等前后缀就是取所有既是前缀又是后缀的子串里最长的那一个的长度。这里有一个新手特别容易懵的地方。计算 next[i] 时考察的是 P[0..i-1] 这个子串的相等前后缀而不是 P[0..i]。比如 next[6]要看的是 P[0..5] abacab 的最长相等前后缀结果是 ab长度 2所以 next[6] 2。这个少看一位的定义是为了让 next[i] 能直接作为失配后的回退位置——因为第 i 位失配时前面 0 到 i-1 位都已经匹配成功了。3.2 逐位推导从 next[0] 到 next[6]下面我完整推导一遍 P abacaba 的 next 数组手把手带大家走一遍这个过程。next[0] 没有前面的子串惯例上设为 -1表示模式串已经退无可退此时文本串指针需要前进一位。next[1] 考察的是 P[0] a 的相等前后缀前缀集合为空后缀集合也为空前面说了要去掉首尾字符所以相等前后缀长度是 0next[1] 0意味着失配后从头开始比较。接下来是核心推导过程我一个位置一个位置来iP[i]考察子串 P[0..i-1]最长相等前后缀长度next[i]0a无无--11ba无002aab无003cabaa114aabac无005babacaa116aabacabab22这里有一个手动推导的小技巧。计算 next[i] 时不需要真的把前缀后缀集合全部列出来只需要从头尾同时往中间比对看最多能匹配多长。比如算 next[6]看 abacab首字母 a 和尾字母 b 不相等那最长相等前后缀长度不可能超过 1不对这里要注意最长相等前后缀不一定要求首尾字符相等。正确的检查方式是先看长度为 1 的前后缀 a 和 b不等再看长度为 2 的前后缀 ab 和 ab相等所以结果是 2。再看长度为 3 的前后缀 aba 和 cab不相等。所以最长就是 2。实际手算的时候从长度 1 开始逐层增加也很容易出错我更推荐的做法是从可能的最大长度开始递减检查。最大长度是 i-1对于 abacab最大是 5但显然前后缀差异很大很快就能排除落到 2 上。熟练之后一眼扫过去就能找到对称的重复片段。4. 代码落地KMP 匹配的完整实现与细节打磨4.1 预处理 next 数组的代码怎么写理解了手动推导接下来就是把思路翻译成代码。计算 next 数组的过程本质上也是一个自我匹配的过程它的巧妙之处在于用两个指针 i 和 jj 表示当前已匹配的前缀长度i 表示正在计算的 next 数组下标。直接看代码def build_next(p): m len(p) nxt [-1] * m i, j 0, -1 while i m - 1: if j -1 or p[i] p[j]: i 1 j 1 nxt[i] j else: j nxt[j] return nxt这段代码的退出条件是 i 到达 m-1因为 next 数组只需要计算到最后一个下标。我初次看这段代码时也觉得很绕这里拆解一下。j 初始化为 -1表示当前没有匹配的前缀。当 p[i] 和 p[j] 相等时说明匹配长度可以加 1所以 i 和 j 同时自增nxt[i] 就记录下了这个长度。当不相等时j 回退到 nxt[j]这个操作和匹配阶段失配时的回退逻辑完全一致。把 next 数组的计算理解成模式串和自己做匹配很多疑问就通了。4.2 匹配阶段实现文本串指针不回退模式串指针灵活跳转预处理完成之后匹配阶段的代码非常简洁def kmp_search(text, pattern): n, m len(text), len(pattern) if m 0: return 0 nxt build_next(pattern) i, j 0, 0 while i n: if j -1 or text[i] pattern[j]: i 1 j 1 else: j nxt[j] if j m: return i - m return -1这里有几个关键点需要特别说明。第一当 j -1 时说明模式串已经回退到了无法再回退的位置此时文本串指针必须向前移动一位模式串指针归零相当于从这一位重新开始匹配。第二当 j 增加到 m 时说明模式串已经完全匹配成功此时文本串指针 i 指向的是匹配末尾的后一位所以起始位置是 i - m。第三如果文本串遍历完还没有返回说明不存在匹配的子串返回 -1。4.3 一个具体的模拟过程把代码跑在例子上理论说得再多不如亲手模拟一遍。用 T abacababacabP abacaba我把匹配过程中关键的指针变化列出来初始状态 i0j0开始逐位比较。T[0..5] 和 P[0..5] 完全匹配i6j6。此时比较 T[6] 和 P[6]T[6] 是 bP[6] 是 a失配。按照 next 数组j 回退到 nxt[6] 2。注意这里文本串的 i 没有动还是 6。接着从 P[2] 开始继续比较P[2] 是 aT[6] 是 b又失配。j 回退到 nxt[2] 0。P[0] 是 aT[6] 是 b还是失配。j 回退到 nxt[0] -1。此时 j -1i 前进到 7j 归 0。从 T[7] 开始重新匹配T[7..13] 恰好与 P[0..6] 完全一致匹配成功返回起始位置 7。这个模拟过程很好地体现了 KMP 的优势i 从 0 到 13 单调递增全程没有回退失配时模式串指针最多跳回几次就能继续前进。对比暴力法在 i6 处失配后要尝试 i1、2、3 等位置每轮都要重新比较前几个字符额外开销是很大的。5. 常见问题与避坑记录这些坑我基本都踩过5.1 next 数组定义不统一导致的混淆关于 next 数组网上有两种常见定义。一种是本文使用的失配后回退的位置即 next[0] -1另一种是最长相等前后缀长度最前面的可以设为 0匹配时失配后拿 next[j-1] 来跳转。这两种定义写出来的代码不一样但核心原理完全相同。新手最容易被这个搞晕看一篇博客是一个写法换一篇又不一样很容易自我怀疑。我的建议是选定一种定义把它的代码写熟、把模拟过程手推一遍形成肌肉记忆。面试时如果面试官问到了先明确自己用的是哪种定义再写出对应的代码这就不会出问题。不要试图同时记忆两种写法容易串。5.2 build_next 里 i 和 j 的边界条件写 build_next 时最容易出错的是循环边界。如果 while 条件写成 i m那么当 i 到达 m-1 时可能还会继续访问 nxt[i1]造成数组越界。标准的写法是 while i m - 1这样 i 最大取到 m-2nxt[i1] 最大取到 nxt[m-1]正好覆盖整个数组。这个边界条件没有技巧就是多写几遍、多跑几个用例就能记住。还有一个常见问题是模式串长度为 1 的情况。此时 build_next 返回的数组是 [-1]匹配循环里能正常处理但也要注意在 kmp_search 开头判断 m 0 的情况——空模式串按惯例返回 0这个边界很多人在笔试时会漏掉。5.3 匹配结束后下一步该怎么走有时候题目不是要求第一次出现的位置而是统计出现次数。比如问 P 在 T 中出现了多少次且允许重叠。这种情况下匹配成功后不能直接返回而是要让 j 回退到 nxt[j] 然后继续匹配。def kmp_count(text, pattern): n, m len(text), len(pattern) if m 0: return 0 nxt build_next(pattern) i, j 0, 0 ans 0 while i n: if j -1 or text[i] pattern[j]: i 1 j 1 else: j nxt[j] if j m: ans 1 j nxt[j] return ans其实这一行 j nxt[j] 是统计重叠匹配的关键。比如模式串 aaa 在文本串 aaaa 中如果不加这行一找到匹配就停了结果只有 1加了之后每次匹配成功就把 j 回退到最长相等前后缀的位置也就是 2这样能找到 2 个重叠的匹配。这是 string matching 类题目里非常常见的变体值得单独记一下。5.4 一个经常被忽视的问题next 数组是逐个递推的不要试图直接看整串有些朋友看了 next[6] 2 之后会想当然地以为 next[7] 和 next[6] 有关联甚至想直接看整串的前后缀。比如 P abacaba整体最长相等前后缀是 aba长度 3但这不意味着 next 数组里会有一个位置的值是 3。事实上next 数组的每个值只依赖前面子串的相等前后缀关系推导是递推的而不是一次性看完整串。理解这一点很重要因为 KMP 的优化本质就是在递推过程中利用了之前已经算好的 next 值来加速而不是每算一个位置都把前缀后缀全部重新比对一遍。build_next 的时间复杂度能够做到 O(m)正是因为这个递推关系。6. 横向对比KMP 之外还有哪些字符串匹配思路6.1 从 KMP 出发看 BM 和 Sunday如果只刷题KMP 基本够用。但实际工程里像文本编辑器里的查找功能、IDE 里的全局搜索用的是更快的匹配算法。BM 算法的思路是从模式串尾部开始比较利用坏字符和好后缀两个规则来决定跳跃距离在真实文本上平均性能比 KMP 更好。Sunday 算法更简单粗暴它关注的是文本串中参与匹配的最后一个字符的后一个字符根据这个字符在模式串中的位置决定跳跃距离。对于普通开发者来说理解这些算法的适用场景比记住实现更重要。KMP 在最坏情况下有稳定的 O(nm) 表现适合对时间复杂度有严格要求的场景BM 和 Sunday 在平均情况下更快但最坏情况下可能退化到 O(n*m)。日常刷题和面试中掌握 KMP 是底线有余力的可以再看看 Sunday它的代码更短某些场景下效率反而更高。6.2 KMP 的变体应用旋转字符串、重复子串判断字符串匹配的经典变体题我至少能想到两个。一个是旋转字符串问题给定两个字符串 s 和 goal判断 s 经过若干次左移右移之后能否变成 goal。做法很简单检查 len(s) len(goal)然后看 goal 是否是 ss 的子串即可这本质上就是 KMP 的一次应用。另一个是重复子串判断判断一个字符串是否由某个子串重复多次构成。更 tricky 的做法是用 KMP 求 next 数组如果 len % (len - next[len]) 0 且 len ! next[len]则存在重复子串。第二道题的原理值得多说一句。next[len] 表示整个字符串的最长相等前后缀长度如果该字符串由一个子串重复多次构成那么 len - next[len] 就是这个基本子串的长度并且 len 一定能被它整除。比如 abababnext[6] 4len - next[len] 等于 2len % 2 0所以存在重复子串 ab。这个推导用到了 next 数组的核心性质能想明白的话对 KMP 的理解就真的到位了。7. 实际刷题中的三个心得7.1 手写推导比直接抄代码重要一百倍我在最初学 KMP 的时候直接看代码觉得懂了但过三天再写就卡壳尤其是 build_next 那段循环。后来我强迫自己在纸上手动推导 next 数组从短串到长串反复推了几轮再回头写代码发现顺了很多。代码是思想的表达思想没建立起来代码永远记不牢。我有一个具体的方法大家也可以试试。拿一个中等的模式串比如 ababaca先手动用笔算出 next 数组然后在代码里让程序打印 next两厢对照。一旦某一位对不上就停下来仔细想为什么。这个过程很痛苦但每一次卡壳都是在加深理解。7.2 用极端用例验证思路写完 KMP 的代码我习惯先用几个极端用例测试空字符串、模式串和文本串完全相同、模式串只出现一次且在所有位置都失配、模式串是单个字符、模式串里有大量重复字符。这些用例能暴露绝大多数边界错误。特别是大量重复字符的场景比如 P aaaaT aaaabaaa如果 next 数组算错一位效率就会退化到接近暴力解。很多人在 LeetCode 上提交失败报的往往就是超出时间限制原因就是 next 数组写错了导致匹配过程的回退逻辑失效实际复杂度退化成 O(n*m)。一看到超时就该条件反射想到是不是失配回退没有接住导致文本串指针在反复比较同一个位置。7.3 把一道题吃透比刷十道题有用每日算法题系列做了这么久我最大的感受是覆盖知识点的方式不是求多而是求透。像 KMP 这种经典算法如果只是背模板过一周就忘如果能把 next 数组的推导逻辑、失配时的回退流程、代码的边界条件都搞明白那么后面遇到类似的字符串匹配题基本都能一通百通。顺便再说一个小技巧实际写代码的时候给变量命名用 text、pattern、nxt 而不是 i、j、t可读性会好很多。尤其是刷题后期回看笔记的时候语义化的变量名能省不少力气。这不算什么高深经验但确实是实际写代码时体会到的差异。