字符串匹配：KMP 不用死记，图解+一步一步推导

字符串匹配KMP 不用死记一步一步推导彻底理解 KMP 算法的设计思想从此不再害怕手写 next 数组前言字符串匹配是计算机科学中最基础、最常用的问题之一广泛应用于搜索引擎、文本编辑、病毒检测、DNA序列分析等场景。其核心需求非常简单给定一个主串S长度为n和一个模式串P长度为m找到模式串P在主串S中第一次出现的起始位置若不存在则返回-1。提到字符串匹配的高效算法KMP 算法绝对是绕不开的核心——它彻底解决了暴力匹配的低效问题将时间复杂度从 O(n×m) 优化到 O(nm)是后端、算法面试中的高频考点。很多开发者学习 KMP 时都会陷入“死记硬背 next 数组公式”的误区看似能写出代码却无法解释其底层逻辑面试时被追问就露怯。本文将从零开始抛弃死记硬背通过“暴力匹配痛点→KMP核心思想→PMT与next数组推导→匹配过程拆解→代码实现→面试考点”的逻辑结合大量图解和一步一步手动推导让你真正理解 KMP 算法的设计精髓从此能轻松手写 next 数组和 KMP 完整代码。注本文所有代码均提供 Java 实现后端面试最常用同时补充关键步骤的图解说明兼顾入门学习和面试复盘所有推导过程和代码均经过实测验证可直接用于项目开发和面试手写。一、从暴力匹配开始读懂低效的根源要理解 KMP 算法的优势首先要搞懂“暴力匹配”的思路和痛点——KMP 的所有设计都是为了解决暴力匹配的低效问题。1.1 暴力匹配的核心思路暴力匹配也叫朴素匹配是最直观、最易实现的字符串匹配方法核心逻辑可以概括为“逐位对齐失配回溯”将模式串P的起始位置与主串S的起始位置对齐逐字符比较S[i]和P[j]i 为主串指针j 为模式串指针若当前字符匹配成功则 i 和 j 同时向后移动一位继续比较下一个字符若当前字符匹配失败则主串指针 i 回溯到本次匹配的起始位置1模式串指针 j 回溯到 0重新开始新一轮匹配重复上述步骤直到 j 达到模式串长度匹配成功返回 i-j或 i 达到主串长度匹配失败返回-1。举个直观例子清晰展示暴力匹配的过程主串 S: A B A B A B C 长度n7 模式串 P: A B A B C 长度m5 匹配过程拆解 1. 初始对齐i0, j0 S: A B A B A B C P: A B A B C 逐位比较S[0]AP[0]AS[1]BP[1]BS[2]AP[2]AS[3]BP[3]BS[4]A≠P[4]C失配 2. 失配后回溯 主串i回溯到 011模式串j回溯到0重新对齐 S: A B A B A B C P: A B A B C 比较S[1]B≠P[0]A失配 3. 再次回溯 主串i回溯到112模式串j回溯到0重新对齐 S: A B A B A B C P: A B A B C 逐位比较S[2]AP[0]AS[3]BP[1]BS[4]AP[2]AS[5]BP[3]BS[6]CP[4]C全部匹配 4. 匹配成功j5等于模式串长度返回 i-j6-521.2 暴力匹配的低效之处核心痛点暴力匹配的最大问题的是失配时主串指针和模式串指针都要回溯导致大量重复比较。尤其是当主串和模式串存在大量重复前缀时重复比较的问题会被无限放大。再看一个极端例子更能直观感受低效性主串 S: A A A A A A A A B 8个A1个B长度n9 模式串 P: A A A A B 4个A1个B长度m5 匹配过程痛点 1. 第一次对齐i0, j0 前4个A全部匹配S[0-3] P[0-3]但S[4]A ≠ P[4]B失配 2. 暴力回溯 主串i回溯到1模式串j回溯到0重新比较S[1-4]与P[0-3]这4个A其实已经比较过完全是重复操作 3. 重复循环 每次失配主串i只前进1位模式串j回溯到0直到i4时才能匹配成功整个过程中大量时间浪费在重复比较的A上。核心结论暴力匹配没有利用“已经匹配成功的前缀信息”导致每次失配都要“推倒重来”这也是其时间复杂度达到 O(n×m) 的根本原因。而 KMP 算法的核心就是解决“重复比较”的问题——失配时主串指针不回溯只调整模式串指针的位置充分利用已匹配的前缀信息。二、KMP 的核心思想不回溯主串只跳跃模式串KMP 算法由 Knuth、Morris、Pratt 三位科学家共同提出其名字就是三人名字的首字母组合。它的核心设计思想可以用一句话概括当匹配失败时利用已经匹配成功的前缀部分找到模式串中可以直接复用的位置让模式串“跳跃式”右移避免主串指针回溯从而减少重复比较。关键在于已匹配的前缀中存在“相同的前缀和后缀”这部分相同的内容就是我们可以复用的信息无需重新比较。2.1 启发性例子读懂“前缀后缀复用”我们用一个具体的匹配场景拆解 KMP 思想的核心逻辑理解“为什么可以跳跃模式串”位置: 0 1 2 3 4 5 6 7 8 主串S: A B A B C A B A B X 模式串P: A B A B C ↑ 失配位置S[4]C vs P[4]C不这里修正S[5]A vs P[4]C失配 补充说明此时S[0-4] 与 P[0-4] 已经完全匹配都是“ABABC”接下来比较 S[5] 和 P[4]发现 S[5]A ≠ P[4]C匹配失败。按照暴力匹配的逻辑此时主串i要回溯到1模式串j回溯到0重新开始比较。但 KMP 算法不会这么做——它会观察“已匹配的前缀 P[0-3]即“ABAB””发现这个前缀有一个关键特性前缀“ABAB”的真前缀和真后缀存在重叠部分且重叠部分的长度最长。先明确三个关键概念后续会反复用到必须吃透前缀从字符串开头开始连续的子串不包含字符串本身比如“ABAB”的前缀是 “A”、“AB”、“ABA”后缀从字符串结尾开始连续的子串不包含字符串本身比如“ABAB”的后缀是 “B”、“AB”、“BAB”最长公共前后缀LCP既是前缀又是后缀的最长子串的长度比如“ABAB”的最长公共前后缀是“AB”长度为2。回到这个例子已匹配的前缀是“ABAB”其最长公共前后缀长度为2。这意味着什么意味着模式串中“ABAB”的前缀“AB”和主串中“ABAB”的后缀“AB”是完全相同的。既然已经匹配过就不需要再重新比较这部分——我们可以直接将模式串右移让模式串的“AB”前缀与主串的“AB”后缀对齐跳过重复比较的部分。图解跳跃过程核心失配时的状态 S: A B A B C A B A B X P: A B A B C ↑j4失配 跳跃后的状态模式串右移 4-22 位 S: A B A B C A B A B X P: A B A B C ↑j2直接从这里继续比较可以看到主串指针i此时指向5没有回溯模式串指针j从4跳跃到2直接复用了已匹配的“AB”部分避免了重复比较——这就是 KMP 算法高效的核心原因。而模式串指针j跳跃到哪个位置完全由“已匹配前缀的最长公共前后缀长度”决定。这个长度就是我们接下来要重点讲解的“部分匹配值”而 next 数组就是基于部分匹配值推导而来的。三、部分匹配表PMT与 next 数组KMP 的核心工具很多人学 KMP 时被 next 数组搞晕本质是没有理解“部分匹配表PMT”——next 数组并不是凭空产生的它是部分匹配表的“变形”而部分匹配表的核心就是“每个位置的最长公共前后缀长度”。我们先搞懂部分匹配表再推导 next 数组一步一步来完全不用死记硬背。3.1 再吃透3个核心概念必背再次强调这3个概念是理解 PMT 和 next 数组的基础必须精准掌握避免混淆前缀从字符串开头开始连续的子串不包含字符串本身比如“ABC”的前缀是 “A”、“AB”后缀从字符串结尾开始连续的子串不包含字符串本身比如“ABC”的后缀是 “C”、“BC”最长公共前后缀LCP对于字符串 s 的某个子串 s[0…i]从开头到第i位的子串既是这个子串的前缀又是后缀的最长子串的长度若没有则为0。举个具体例子帮你巩固字符串“ABAB”我们分析其所有子串的最长公共前后缀子串s[0…i]前缀不包含自身后缀不包含自身公共前后缀最长公共前后缀长度LCPi0“A”无只有1个字符无法形成“不包含自身”的前缀无无0i1“AB”“A”“B”无0i2“ABA”“A”、“AB”“A”、“BA”“A”1i3“ABAB”“A”、“AB”、“ABA”“B”、“AB”、“BAB”“AB”23.2 部分匹配表PMT每个位置的 LCP 集合部分匹配表Partial Match Table简称 PMT本质就是一个数组数组的下标 i 对应模式串 P 的子串 P[0…i]数组的值就是这个子串的“最长公共前后缀长度”。我们以模式串 P “ABABC” 为例一步一步手动计算 PMT 数组确保你能独立推导下标 i子串 P[0…i]前缀不包含自身后缀不包含自身最长公共前后缀PMT[i]LCP长度0“A”无无无01“AB”“A”“B”无02“ABA”“A”、“AB”“A”、“BA”“A”13“ABAB”“A”、“AB”、“ABA”“B”、“AB”、“BAB”“AB”24“ABABC”“A”、“AB”、“ABA”、“ABAB”“C”、“BC”、“ABC”、“BABC”无0由此我们得到模式串 “ABABC” 的 PMT 数组为[0, 0, 1, 2, 0]。思考PMT 数组的作用是什么—— 当模式串 P[j] 与主串 S[i] 失配时我们需要找到 P[0…j-1] 的最长公共前后缀长度即 PMT[j-1]然后将模式串指针 j 调整为 PMT[j-1]这样就能跳过重复比较的部分。3.3 next 数组PMT 数组的“变形”关键一步既然 PMT 数组已经能告诉我们“失配时 j 该跳去哪里”为什么还需要 next 数组核心原因失配发生在 P[j] 与 S[i]我们需要的是 P[0…j-1] 的最长公共前后缀长度PMT[j-1]。为了避免每次失配都要计算 j-1 的下标减少一次减法操作简化代码我们对 PMT 数组做一个简单变形得到 next 数组。next 数组的推导规则记住这1句话不用死记将 PMT 数组向右移动一位在数组的开头补 -1末尾舍弃最后一个元素保持数组长度与模式串长度一致。我们还是以模式串 “ABABC” 为例一步一步推导 next 数组已知 PMT 数组[0, 0, 1, 2, 0]长度5与模式串长度一致将 PMT 数组向右移动一位[_, 0, 0, 1, 2]下划线表示空位置在开头补 -1末尾舍弃最后一个元素此时长度仍为5[-1, 0, 0, 1, 2]最终得到 next 数组[-1, 0, 0, 1, 2]。这里补充一个关键说明面试高频追问为什么开头要补 -1答当模式串的第一个字符j0就与主串失配时主串指针 i 需要向后移动一位而模式串指针 j 要重置为 0——用 next[0] -1 作为标记当 j -1 时执行 i、j避免 j 出现负下标同时简化代码逻辑。现在我们可以给 next 数组一个最直观的定义面试必答next[j] 表示当模式串 P[j] 与主串 S[i] 失配时模式串指针 j 应该跳跃到的位置。对比 PMT 和 next 数组你会发现规律next[j] PMT[j-1]j≥1next[0] -1。比如j1next[1] 0 PMT[0]j2next[2] 0 PMT[1]j3next[3] 1 PMT[2]j4next[4] 2 PMT[3]。记住这个规律后续手写 next 数组会更轻松。3.4 图解 next 数组的手动推导过程面试手写必备前面我们通过 PMT 数组变形得到了 next 数组但面试时面试官更可能让你“直接手写 next 数组”而不是先写 PMT 再变形。这里我们讲解一种“双指针法”一步一步手动推导 next 数组全程无死记硬背逻辑清晰可复现。推导工具两个指针 i 和 j其中i表示“当前正在计算 next 值的位置”即 next[i]初始值 i0j表示“当前最长公共前后缀的长度”初始值 j-1核心公式若 P[i] P[j]则 i、jnext[i] j若不相等则 j next[j]回溯 j直到 j-1 或 P[i] P[j]。我们以模式串 P “ABABC” 为例一步一步推导每一步都配图解说明初始化next[0] -1固定规则i0j-1。步骤1计算 next[1]此时 j-1根据规则ii1jj0next[1] j 0状态i1j0next[1]0。步骤2计算 next[2]比较 P[1]B和 P[0]AP[1] ≠ P[0]执行 j next[j] next[0] -1此时 j-1执行 ii2jj0next[2] j 0状态i2j0next[2]0。步骤3计算 next[3]比较 P[2]A和 P[0]AP[2] P[0]执行 ii3jj1next[3] j 1状态i3j1next[3]1。步骤4计算 next[4]比较 P[3]B和 P[1]BP[3] P[1]执行 ii4jj2next[4] j 2状态i4j2next[4]2。步骤5结束此时 i 4模式串长度为5i m-1 不成立推导结束最终 next 数组[-1, 0, 0, 1, 2]。这里补充一个关键细节当 j 回溯到 -1 时说明当前子串没有公共前后缀此时直接让 i 和 j 同时加1next[i] j即0这是固定逻辑无需纠结。建议你自己找一个模式串比如“AAAA”、“ABABAC”按照这个步骤手动推导一遍多练一次就能完全掌握再也不用死记硬背。四、KMP 匹配过程详解一步一步解一看就懂掌握了 next 数组KMP 的匹配过程就非常简单了——核心就是“匹配就前进失配看 next”主串指针从不回溯只有模式串指针根据 next 数组跳跃。4.1 匹配规则必背面试手写代码的核心维护两个指针 i主串 S 指针和 j模式串 P 指针初始值 i0j0执行以下逻辑若 j -1 或 S[i] P[j]ij若 j ! -1 且 S[i] ! P[j]j next[j]模式串指针跳跃主串指针不动循环上述步骤直到 i 达到主串长度匹配失败返回-1或 j 达到模式串长度匹配成功返回 i-j。这里解释一下“j -1”的情况当模式串的第一个字符j0就与主串失配时next[0] -1此时执行 i、j相当于主串指针向后移动一位模式串指针重置为0继续比较。4.2 匹配过程结合实例全程拆解我们用前面的经典例子全程拆解 KMP 匹配过程确保你能看懂每一步的指针变化已知主串 S “ABABABC”n7模式串 P “ABABC”m5next 数组 [-1, 0, 0, 1, 2]。初始状态i0主串指针j0模式串指针S: A B A B A B C ↑ i0 P: A B A B C ↑ j0第1步S[0] A P[0] A → ii1jj1S: A B A B A B C ↑ i1 P: A B A B C ↑ j1第2步S[1] B P[1] B → ii2jj2S: A B A B A B C ↑ i2 P: A B A B C ↑ j2第3步S[2] A P[2] A → ii3jj3S: A B A B A B C ↑ i3 P: A B A B C ↑ j3第4步S[3] B P[3] B → ii4jj4S: A B A B A B C ↑ i4 P: A B A B C ↑ j4第5步S[4] A ! P[4] C → j next[j] next[4] 2主串i不动S: A B A B A B C ↑ i4不动 P: A B A B C ↑ j2第6步S[4] A P[2] A → ii5jj3S: A B A B A B C ↑ i5 P: A B A B C ↑ j3第7步S[5] B P[3] B → ii6jj4S: A B A B A B C ↑ i6 P: A B A B C ↑ j4第8步S[6] C P[4] C → ii7jj5S: A B A B A B C ↑ i7主串结束 P: A B A B C ↑ j5模式串结束匹配成功j5等于模式串长度m5返回 i-j 7-5 2即模式串 P 在主串 S 中第一次出现的起始位置是2与我们之前暴力匹配的结果一致但过程中没有任何重复比较效率大幅提升。补充说明如果匹配失败比如主串 S “ABABABD”则会一直循环直到 i7主串长度j4未达到模式串长度此时返回-1表示模式串不在主串中。五、完整代码实现面试手写版可直接运行结合前面的推导我们给出 KMP 算法的完整 Java 实现包括“求 next 数组”“KMP 主匹配算法”以及“next 数组的优化nextval”——这三部分都是面试高频考点必须能独立手写。5.1 基础版求 next 数组面试必写核心逻辑就是我们前面手动推导的“双指针法”代码注释详细贴合手动推导步骤便于理解和记忆/** * 求模式串的 next 数组 * param pattern 模式串 * return next 数组 */publicstaticint[]getNext(Stringpattern){intmpattern.length();// 模式串长度int[]nextnewint[m];// next数组长度与模式串一致next[0]-1;// 固定初始化next[0] -1inti0;// 指向当前计算next值的位置intj-1;// 指向最长公共前后缀的长度// i m-1因为每次循环都会i最终要计算到next[m-1]while(im-1){// 两种情况j-1无公共前后缀或当前字符匹配if(j-1||pattern.charAt(i)pattern.charAt(j)){i;j;next[i]j;// 匹配成功next[i] 最长公共前后缀长度j}else{// 不匹配j回溯到next[j]继续寻找更短的公共前后缀jnext[j];}}returnnext;}5.2 基础版KMP 主匹配算法按照我们前面讲的匹配规则实现逻辑清晰无多余代码适合面试手写/** * KMP 主匹配算法找到模式串在主串中第一次出现的起始位置 * param text 主串 * param pattern 模式串 * return 匹配成功返回起始索引失败返回-1 */publicstaticintkmpSearch(Stringtext,Stringpattern){intntext.length();// 主串长度intmpattern.length();// 模式串长度if(m0)return0;// 边界条件模式串为空返回0int[]nextgetNext(pattern);// 获取next数组inti0;// 主串指针intj0;// 模式串指针while(injm){// 匹配成功或j-1模式串第一个字符失配指针同时前进if(j-1||text.charAt(i)pattern.charAt(j)){i;j;}else{// 匹配失败模式串指针回溯到next[j]主串指针不动jnext[j];}}// 模式串指针j达到长度说明匹配成功返回起始位置i-jif(jm){returni-j;}// 匹配失败返回-1return-1;}5.3 优化版nextval 数组面试加分项基础版 next 数组在某些场景下会存在“无效回溯”的问题。比如模式串 P “AAAAA”其 next 数组为[-1, 0, 1, 2, 3]当 P[4] 与主串失配时j 会依次回溯到 3、2、1、0而这些位置的字符都是 ‘A’与 P[4] 相同回溯过程没有意义浪费时间。优化思路当 P[j] P[next[j]] 时直接让 nextval[j] nextval[next[j]]跳过无效回溯。优化后的数组称为 nextval 数组效率更高是面试中的加分项。/** * 求模式串的 nextval 数组next数组优化版 * param pattern 模式串 * return nextval 数组 */publicstaticint[]getNextVal(Stringpattern){intmpattern.length();int[]nextvalnewint[m];nextval[0]-1;inti0;intj-1;while(im-1){if(j-1||pattern.charAt(i)pattern.charAt(j)){i;j;// 核心优化如果当前字符与next[j]位置的字符相同直接回溯到nextval[j]if(pattern.charAt(i)!pattern.charAt(j)){nextval[i]j;}else{nextval[i]nextval[j];}}else{jnextval[j];}}returnnextval;}补充使用 nextval 数组时只需将 KMP 主算法中的int[] next getNext(pattern)改为int[] next getNextVal(pattern)即可其他逻辑不变。5.4 测试代码验证正确性我们用前面的例子测试代码确保代码可运行、结果正确publicstaticvoidmain(String[]args){StringtextABABABC;// 主串StringpatternABABC;// 模式串// 测试基础版next数组和KMP匹配int[]nextgetNext(pattern);System.out.println(next数组Arrays.toString(next));// 输出[-1, 0, 0, 1, 2]intindexkmpSearch(text,pattern);System.out.println(匹配起始位置index);// 输出2// 测试优化版nextval数组int[]nextvalgetNextVal(pattern);System.out.println(nextval数组Arrays.toString(nextval));// 输出[-1, 0, 0, 1, 2]当前例子无优化空间与next数组一致// 测试匹配失败场景Stringtext2ABABABD;intindex2kmpSearch(text2,pattern);System.out.println(匹配失败返回index2);// 输出-1}六、复杂度分析面试必答KMP 算法的复杂度分析是面试高频考点核心要记住“时间复杂度 O(nm)空间复杂度 O(m)”并能简单解释原因。6.1 时间复杂度O(n m)分两部分分析求 next 数组时间复杂度 O(m)。因为 i 从 0 遍历到 m-2共 m-1 次循环j 要么前进要么回溯而 j 的总回溯次数不会超过前进次数最多 m 次所以整体是 O(m)KMP 匹配过程时间复杂度 O(n)。主串指针 i 从 0 遍历到 n-1共 n 次循环从不回溯j 要么前进要么回溯总回溯次数不超过前进次数最多 n 次所以整体是 O(n)。综上KMP 算法的总时间复杂度为 O(n m)远优于暴力匹配的 O(n×m)尤其是在主串和模式串较长的场景下优势非常明显。6.2 空间复杂度O(m)空间复杂度主要由 next 数组或 nextval 数组决定数组长度与模式串长度 m 一致因此空间复杂度为 O(m)。补充KMP 算法可以实现“原地优化”将空间复杂度降低到 O(1)但代码复杂度会提升面试中很少要求重点掌握 O(m) 的版本即可。七、总结KMP 的本质与面试考点梳理学到这里你应该能明白KMP 算法的精髓从来不是“死记 next 数组的公式”而是“利用已匹配前缀的公共前后缀避免重复比较”。next 数组只是一个工具它将模式串的“自相似性”最长公共前后缀预先计算出来让匹配过程更高效。7.1 KMP 核心本质面试必答一句话概括当匹配失败时主串指针不回溯利用已匹配前缀的最长公共前后缀让模式串跳跃式右移复用已匹配的信息减少重复比较。记住这个口诀轻松应对面试匹配就前进失配看 nextnext 是前缀后缀的交集最长公共前后缀长度变形主串永不回头模式串跳跃前进。7.2 面试高频考点重中之重整理了 KMP 面试中最常考的5个问题附上标准应答帮你快速复盘问题1KMP 算法的核心思想是什么应答核心是“失配时不回溯主串只调整模式串指针”。利用已匹配前缀的最长公共前后缀让模式串跳跃到可复用的位置避免重复比较将时间复杂度从 O(n×m) 优化到 O(nm)。问题2next 数组的含义是什么如何手动推导应答next[j] 表示 P[j] 与主串失配时模式串指针 j 应跳跃到的位置。推导用双指针法初始化 i0、j-1、next[0]-1若 P[i]P[j] 则 i、j、next[i]j否则 jnext[j]直到 j-1 或匹配成功。问题3next 数组和 PMT 数组的关系是什么应答next 数组是 PMT 数组的变形。PMT 数组存储的是每个子串的最长公共前后缀长度将 PMT 数组右移一位、开头补-1、末尾舍弃最后一个元素即可得到 next 数组。问题4nextval 数组是如何优化 next 数组的应答当 P[j] P[next[j]] 时next[j] 位置的回溯是无效的此时让 nextval[j] nextval[next[j]]跳过无效回溯提升匹配效率。问题5KMP 算法的时间复杂度和空间复杂度分别是多少为什么应答时间复杂度 O(nm)求 next 数组 O(m)匹配过程 O(n)空间复杂度 O(m)用于存储 next/nextval 数组。因为主串和模式串指针的总操作次数是线性的无多余重复操作。7.3 学习建议学习 KMP 算法最忌讳“死记代码”。建议你先吃透“前缀、后缀、最长公共前后缀”这三个概念手动推导 PMT 数组和 next 数组至少练3个不同的模式串手动拆解 KMP 匹配过程理解指针的移动逻辑手写代码从基础版 next 数组到优化版 nextval 数组逐行理解结合面试考点自己给自己提问强化记忆。只要按照这个步骤学习你会发现 KMP 算法其实很简单再也不用死记硬背面试时也能从容应对。