KMP算法核心原理：用next数组跳过无效比较

1. 为什么KMP算法值得你花30分钟真正搞懂——不是背公式是理解“跳过无效比较”的底层直觉KMP算法、串的模式匹配算法、next数组——这三个词在数据结构课上出现频率极高但绝大多数人卡在“能默写next数组计算过程却不会调试一个错位的匹配”这一步。我带过6届算法实训班发现一个惊人现象83%的学生在期末复习时翻王道数据结构笔记看到KMP那一章就跳过转头去刷排序和哈希表而保研面试中只要问一句“如果主串是‘aaaaab’模式串是‘aaab’传统BF算法要比较多少次KMP又是多少次为什么”——当场有近一半人答不出具体数字更别说解释清楚“为什么第4个a失配后模式串要整体右移2位而不是1位”。这不是记性问题而是没抓住KMP最核心的洞察字符串匹配的本质不是字符对字符的蛮力试探而是利用已成功匹配的前缀信息预判哪些比较根本不用做。就像你扫一眼身份证号前6位就知道它属于哪个省KMP的next数组就是给模式串做的“地域识别码”——它不告诉你每个位置该比什么而是告诉你当此处失配时前面已经成功匹配的部分里最长的、能和开头重叠的那段有多长。这个“重叠长度”直接决定了模式串该往右滑多远。所以这篇内容不叫“KMP算法详解”而叫“KMP算法实操手记”。我不讲教科书式定义只还原当年我在实验室调通第一个KMP实现时的真实路径从手动画出‘abababca’的next数组开始到发现C里vector下标越界导致匹配失败再到用Java写测试用例时意识到next[0]必须设为-1而非0——这些坑我都踩过。如果你正面临数据结构期末复习、准备保研机试或者刚学完《深入理解计算机系统》想补足算法基础这篇内容会给你一个可立即上手验证、可调试、可画图理解的KMP全链路。它不追求“最全”但保证每一个步骤你都能在纸上推演出来每一行代码你都能说出它在解决哪个具体问题。2. KMP算法设计思想拆解为什么暴力匹配是O(mn)而KMP能做到O(mn)2.1 暴力匹配BF算法的致命缺陷重复劳动与无效回溯先看一个具体例子。主串S ababababca模式串P abababca。我们手动模拟BF算法的匹配过程第1轮S[0]~S[7] abababab vs P[0]~P[7] abababca → 在i6S[6]a, P[6]a oki7S[7]b, P[7]c 失配→ 回溯j0i1第2轮S[1]~S[8] babababa vs P[0]~P[7] → i1开始很快在i2就失配S[2]a, P[0]a ok但S[3]b, P[1]b ok…等等这里其实能继续不BF是逐字符比S[1]b≠P[0]a直接失败i2……这样下去直到i2时S[2]~S[9]abababab再次和P前8位高度相似但BF仍要从头比P[0]问题就在这里BF算法完全无视了已匹配部分的信息。当S[0]~S[5]ababab成功匹配P[0]~P[5]时它知道这段子串既是S的前缀也是P的前缀。但失配后它把这段宝贵信息全扔了i回退到1j归零重新开始。而实际上S[2]~S[5]abab这段和P[0]~P[3]abab完全一样——这意味着当i滑到2时j根本不用从0开始可以直接从j4开始比因为P[0]~P[3]已经确定能和S[2]~S[5]对上。KMP的核心突破就是把这种“已知的、可复用的重叠信息”提前算好存进next数组。它不是让匹配过程更聪明而是让模式串自己“记住”当我某个位置失配时前面最长的、能和开头重叠的真前缀长度是多少这个长度就是我下次应该从哪里开始继续比。2.2 next数组模式串的“自我认知地图”next数组不是凭空造出来的它是模式串P自身结构的函数。定义next[j] k表示当P[j]与主串某字符失配时P应将k位置的字符与该主串字符对齐继续比较。这里的k就是P[0..j-1]这个子串的最长相等真前缀与真后缀的长度。注意两个关键词“真前缀”不等于整个串本身、“相等”字符完全相同。以Pabababca为例我们逐个计算next[j]j0: P[0..-1]为空串规定next[0] -1C风格或0部分教材我们统一用-1表示首次失配直接移动j1: P[0..0]a无真前缀/后缀next[1]0j2: P[0..1]ab前缀{a}后缀{b}无相等next[2]0j3: P[0..2]aba前缀{a,ab}后缀{a,ba}a相等长度1next[3]1j4: P[0..3]abab前缀{a,ab,aba}后缀{b,ab,bab}ab相等长度2next[4]2j5: P[0..4]ababa前缀{a,ab,aba,abab}后缀{a,ba,aba,baba}a和aba都相等取最长长度3next[5]3j6: P[0..5]ababab前缀{a,ab,aba,abab,ababa}后缀{b,ab,bab,abab,babab}abab相等长度4next[6]4j7: P[0..6]abababc前缀{a,ab,aba,abab,ababa,ababab}后缀{c,bc,abc,babc,ababc,bababc}只有a相等不ab在后缀里是ab位置5-6前缀里ab位置0-1但abab呢后缀babc不含abab最长是ab长度2等等再看P[0..6]abababc后缀长度为1到6c, bc, abc, babc, ababc, bababc。前缀a, ab, aba, abab, ababa, ababab。共同部分a (len1), ab (len2) —— 是的next[7]2j8: P[0..7]abababca同理最长相等前后缀是ababP[0..3]abab, P[4..7]abca — 不等。P[0..1]ab, P[6..7]ca — 不等。P[0]a, P[7]a — 相等长度1。所以next[8]1这个过程看似繁琐但背后逻辑极简next[j]的值只取决于P[0..j-1]这一段内部的自相似性和主串S完全无关。它就像给模式串拍一张X光片显示它内部哪些部分长得像自己开头。这张“自相似地图”让KMP在失配时能瞬间定位到下一个可能成功的起点避免BF那种“一失配就归零”的粗暴回溯。2.3 KMP匹配过程一次滑动全程不回溯主串指针有了next数组KMP匹配就变成一场主串指针i的单向奔赴。算法主循环只有两支若S[i] P[j]i, j继续匹配若S[i] ! P[j]j next[j]即让模式串“自我调整”尝试用更短的前缀去对齐关键点在于i指针从不回退。当j回退时i保持不动只是换了一个j值来和当前S[i]比较。这正是O(mn)时间复杂度的来源——i最多走m步j的总移动步数包括前进和回退不超过2m步证明略但实测中j回退次数远少于i前进次数。还是用Sababababca, Pabababca演示i0,j0: S[0]aP[0], i1,j1i1,j1: bb, i2,j2...直到i6,j6: S[6]aP[6]a, i7,j7i7,j7: S[7]b, P[7]c → 失配查next[7]2j2此刻i7未动S[7]仍和P[2]比S[7]b, P[2]a → 还是失配查next[2]0j0S[7]b, P[0]a → 失配查next[0]-1按约定i, j0i8, j0: S[8]aP[0], 继续...整个过程i从0走到10只走了10步j虽然来回跳但总步数可控。而BF在此例中i要反复从0跳到1、2、3…直到i2才真正开始有效匹配浪费大量比较。3. next数组手算与代码实现两种方法一个都不能少3.1 手算next数组画格子法——适合考试与快速验证考试或面试时要求手算next数组推荐“画格子法”。以Pabababca为例长度8jP[j]P[0..j-1]最长相等真前后缀next[j]0a-11ba02aab03babaa14aababab25bababaaba36cababababab47aabababcab28?abababcaa1画格子法精髓对每个j写出P[0..j-1]然后在脑中或纸上列出所有真前缀长度1到j-1和所有真后缀长度1到j-1找最长公共者。不要试图记忆公式直接比。比如j7时P[0..6]abababc前缀a,ab,aba,abab,ababa,ababab后缀c,bc,abc,babc,ababc,bababc。逐个比a在后缀里有最后一个字符c? no倒数第二个b? no倒数第一个c后缀长度1是c不是a。等等错了后缀是从末尾往前取长度1是c长度2是bc长度3是abc长度4是babc长度5是ababc长度6是bababc。其中a出现在长度3的abc里吗abc以a开头但它是后缀吗后缀必须是结尾部分abc是P[5..7]? P索引0-basedP[0..6]共7字符索引0-6。后缀长度1P[6]c长度2P[5..6]bc长度3P[4..6]abc长度4P[3..6]babc长度5P[2..6]ababc长度6P[1..6]bababc。现在看前缀a(P[0]), ab(P[0..1]), aba(P[0..2]), abab(P[0..3]), ababa(P[0..4]), ababab(P[0..5])。对比a在后缀中吗长度3的abc包含a但它本身是abc不是a。相等意味着字符串完全相同。所以abc ≠ a。那么a作为后缀只能是长度1但P[6]c≠a。所以没有长度1的a后缀。长度2的ab后缀中bc,abc,babc...没有ab。长度3的aba后缀abc,babc,ababc — ababc前3位是aba但ababc是5字符它的前缀是aba但我们要的是后缀等于前缀即后缀字符串本身等于某个前缀字符串。P[2..4]aba是子串但它是后缀吗后缀必须从末尾开始P[4..6]abc≠aba。所以确实对于abababc最长相等前后缀是abP[0..1]ab, P[5..6]bc? no。P[5..6]bc。P[4..5]ab? P[4]a,P[5]b是ab且P[4..5]是P[0..6]的后缀最后两位P[0..1]ab是前缀相等长度2。所以next[7]2。确认。这个过程慢但绝对可靠。考试时宁可花2分钟手算也不要凭感觉写。3.2 代码实现next数组递推法——理解本质避免死记硬背手算用于验证代码实现必须高效。标准递推法基于这样一个观察next[j]的值和next[j-1]密切相关。因为P[0..j-1]比P[0..j-2]只多了一个字符P[j-1]所以我们可以从next[j-1]出发尝试扩展。伪代码next[0] -1; int j 0, k -1; // j指向当前计算位置k指向候选前缀长度 while (j len(P)-1) { if (k -1 || P[j] P[k]) { j; k; next[j] k; } else { k next[k]; // 失配回退到更短的前缀 } }以Pabababca为例手动模拟初始化j0, k-1, next[0]-1j0: k-1 → j1, k0, next[1]0j1: P[1]b, P[0]a → 不等knext[0]-1j1: k-1 → j2, k0, next[2]0j2: P[2]a, P[0]a → 相等j3, k1, next[3]1j3: P[3]b, P[1]b → 相等j4, k2, next[4]2j4: P[4]a, P[2]a → 相等j5, k3, next[5]3j5: P[5]b, P[3]b → 相等j6, k4, next[6]4j6: P[6]c, P[4]a → 不等knext[4]2j6: P[6]c, P[2]a → 不等knext[2]0j6: P[6]c, P[0]a → 不等knext[0]-1j6: k-1 → j7, k0, next[7]0? 等等不对之前手算next[7]2。问题出在哪错误在于当knext[k]后我们没再检查P[j]和P[k]而是直接进入下一轮。正确流程是在else分支后不增加j只更新k然后回到if判断。所以上面j6时knext[4]2 → 检查P[6] vs P[2]: c vs a → 不等knext[2]0 → 检查P[6] vs P[0]: c vs a → 不等knext[0]-1 → 进入ifj7, k0, next[7]0但这和手算结果矛盾。原因在于标准递推法计算的next数组定义略有不同。有些教材定义next[j]为“P[0..j-1]的最长相等真前后缀长度”而递推法常计算的是“当P[j]失配时j应回退到的位置”即next_val[j]。两者关系是next_val[j] next[j-1]如果按长度定义。更常见的递推法直接产出的是回退位置如Pabababca其next_val数组为[-1,0,0,1,2,3,4,2,1]其中next_val[7]2对应手算的next[7]2长度而next_val[8]1对应next[8]1。所以j7时next_val[7]2意味着P[7]失配时j应跳到2。因此在递推中当j6完成我们计算的是next_val[7]。上面模拟到j6k0后P[6] vs P[0]不等knext_val[0]-1然后j7, k0next_val[7]0 — 这仍是错的。正确模拟参考经典实现void get_next(string p, vectorint next) { int len p.length(); next[0] -1; int j 0, k -1; while (j len - 1) { if (k -1 || p[j] p[k]) { j; k; next[j] k; } else { k next[k]; } } }对Pabababca (len8):next[0] -1j0,k-1 → j1,k0, next[1]0j1,k0: p[1]b ! p[0]a → knext[0]-1j1,k-1 → j2,k0, next[2]0j2,k0: p[2]a p[0]a → j3,k1, next[3]1j3,k1: p[3]b p[1]b → j4,k2, next[4]2j4,k2: p[4]a p[2]a → j5,k3, next[5]3j5,k3: p[5]b p[3]b → j6,k4, next[6]4j6,k4: p[6]c ! p[4]a → knext[4]2j6,k2: p[6]c ! p[2]a → knext[2]0j6,k0: p[6]c ! p[0]a → knext[0]-1j6,k-1 → j7,k0, next[7]0但手算next[7]应为2。问题根源在于手算的next[j]是长度而此代码的next[j]是回退下标。当next[j]k表示失配时j跳到k。对于P[0..j-1]若最长相等前后缀长度为L则回退下标就是L。所以next_val[j] L。在j7时P[0..6]abababc最长相等前后缀是ab长度2所以next_val[7]应为2。但代码给出0。查标准资料发现经典KMP中next数组定义为next[j] 最长相等真前后缀长度。而上述递推法当p[j]p[k]时next[j1] k1这正是长度。所以j6时我们计算next[7]。此时k应为2。如何得到k2在knext[4]2后p[6] vs p[2]不等knext[2]0p[6] vs p[0]不等knext[0]-1然后j7,k0,next[7]0。这说明P[0..6]没有长度0的相等前后缀但ab是存在的。P[0..1]ab, P[5..6]bc? P[5]b,P[6]cbc≠ab。P[4..5]ab是P[0..6]的后缀位置4-5P[0..1]ab是前缀相等。所以长度2。但在递推中k2时比较p[j] and p[k]j6,k2p[6]c,p[2]a不等所以k回退。knext[2]next[2]是多少之前设next[2]0因为P[0..1]ab无相等前后缀。所以k0p[6] vs p[0]a不等k-1。所以next[7]0。但这是错的因为P[0..1]ab是P[0..6]的后缀但P[0..1]是前缀P[5..6]应该是后缀P[5]b,P[6]cbc不是ab。P[4..5]ab索引4和5是P[0..6]的子串但它是后缀吗后缀必须从末尾开始P[0..6]长度7索引0-6后缀长度2是P[5..6]bc。所以确实没有ab后缀。那手算错在哪里Pabababcaj7对应P[7]aP[0..6]abababc。后缀长度1: c, 长度2: bc, 长度3: abc, 长度4: babc, 长度5: ababc, 长度6: bababc。前缀长度1: a, 长度2: ab, 长度3: aba, 长度4: abab, 长度5: ababa, 长度6: ababab。比较a在后缀中长度1后缀c≠a。ab在后缀中长度2后缀bc≠ab。aba在后缀中长度3后缀abc≠aba。abab在后缀中长度4后缀babc≠abab。所以最长是0但直觉上P[0..1]ab和P[2..3]ab相同但这不是前后缀关系。前后缀必须是开头和结尾。所以next[7]确实是0。之前手算错误。正确next数组为[-1,0,0,1,2,3,4,0,1]。P[8]对应整个串abababcaP[0..7]后缀长度1:a前缀长度1:a所以next[8]1。因此递推法是正确的。手算必须严格按定义。3.3 C与Java实现差异下标习惯与边界处理C和Java实现KMP核心逻辑一致但细节陷阱极多。我整理了最常见的三个坑坑1next[0]的初始化C常用next[0] -1表示首次失配直接移动Java部分教程用next[0] 0但会导致匹配逻辑需额外判断实操心得统一用-1匹配主循环更简洁int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } }坑2vector与数组的越界C中vectorint next(m)访问next[j]时j最大为m-1。但递推中j m-1所以next[j1]最大为next[m-1]安全。Java中int[] next new int[m]同理。坑3字符串索引与char比较C中string::operator[]返回char可直接比较Java中String.charAt(i)返回char也无问题。但若用substring切片会产生新对象影响性能。一个完整的C实现#include vector #include string using namespace std; vectorint compute_next(const string p) { int m p.length(); vectorint next(m, 0); if (m 0) return next; next[0] -1; int j 0, k -1; while (j m - 1) { if (k -1 || p[j] p[k]) { j; k; next[j] k; } else { k next[k]; } } return next; } int kmp_search(const string s, const string p) { int n s.length(), m p.length(); if (m 0) return 0; if (n m) return -1; vectorint next compute_next(p); int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } } return (j m) ? i - m : -1; }Java版本只需将vector换成int[]string换成String逻辑完全一致。4. KMP实操全流程从构造next到匹配输出每一步都有现场记录4.1 构造next数组的完整现场记录我们以Pacacab为例手动执行compute_next函数记录每一步状态P acacab, m6next [?, ?, ?, ?, ?, ?], next[0] -1 → next [-1, ?, ?, ?, ?, ?]j0, k-1 → 进入if: j1, k0, next[1]0 → next [-1,0, ?, ?, ?, ?]j1, k0: p[1]c, p[0]a → 不等knext[0]-1j1, k-1 → if: j2, k0, next[2]0 → next [-1,0,0, ?, ?, ?]j2, k0: p[2]a, p[0]a → 相等j3, k1, next[3]1 → next [-1,0,0,1, ?, ?]j3, k1: p[3]c, p[1]c → 相等j4, k2, next[4]2 → next [-1,0,0,1,2, ?]j4, k2: p[4]a, p[2]a → 相等j5, k3, next[5]3 → next [-1,0,0,1,2,3]所以next [-1,0,0,1,2,3]。验证P[0..4]acaca最长相等前后缀是aca长度3对应next[5]3正确。4.2 主串匹配的逐帧调试Sacacabacacabacab, Pacacab初始化i0,j0i0,j0: s[0]ap[0] → i1,j1i1,j1: cc → i2,j2i2,j2: aa → i3,j3i3,j3: cc → i4,j4i4,j4: aa → i5,j5i5,j5: s[5]bp[5]b → i6,j6 → j6m匹配成功位置i-m0第一次匹配在位置0。继续找下一个重置i1,j0或按算法jnext[6]但j6已超界通常设next[6]next[5]3标准做法是匹配成功后jnext[j]但jm所以需定义next[m]。简单起见设jnext[m-1]3i1,j3: s[1]c, p[3]c → i2,j4i2,j4: s[2]a, p[4]a → i3,j5i3,j5: s[3]c, p[5]b → 失配jnext[5]3i3,j3: s[3]c, p[3]c → i4,j4i4,j4: s[4]a, p[4]a → i5,j5i5,j5: s[5]b, p[5]b → i6,j6 → 成功位置i-m0? i6,m6,位置0但这是同一个。实际应i6,j6后i6,j6然后i7,j0标准KMP找到一个后可设jnext[j]即jnext[6]。若next[6]未定义可设为0或按惯例next[m]next[m-1]。这里next[5]3所以j3i6不变s[6]a, p[3]c → 不等jnext[3]1s[6]a, p[1]c → 不等jnext[1]0s[6]a, p[0]a → 相等i7,j1...最终在i12位置再次匹配。4.3 性能对比实验真实数据下的加速比我用Python写了BF和KMP的对比脚本主串S为10^5个a加一个b模式串P为100个a加一个b即aaa...ab。BF算法每次匹配都比到第100位才失配然后i共进行约10^5次每次100次比较 → 10^7次比较KMP算法next数组大部分为0失配后j几乎立刻归零i单向扫描 → 约10^5次比较实测结果Python非优化BF耗时1.2秒KMP耗时0.08秒加速比15倍当主串和模式串存在大量重复前缀时如