【LeetCode刷题日记】一篇彻底搞懂KMP算法（附LeetCode28.详解）及原理剖析

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺摘要KMP算法是字符串匹配中的经典算法通过利用匹配失败后的信息避免主串指针的回溯将时间复杂度从暴力匹配的O(n×m)优化到O(nm)。本文从核心概念入手详细讲解了前缀与后缀的定义、最长相等前后缀的计算方法以及next数组的四种实现方式经典版、统一减一版、nextval优化版、PMT版并通过图解和代码示例展示构建过程。文章还包含LeetCode 28题的完整题解、多个生动比喻帮助理解以及时间复杂度的详细分析。无论你是初学者还是准备面试本文都能帮你彻底搞懂KMP算法的理论基础与代码实现。KMP算法理论基础KMPKnuth-Morris-Pratt算法是一种高效的字符串匹配算法由Knuth、Morris和Pratt三位大神共同发明。它通过利用模式串自身的重复模式避免不必要的回溯将时间复杂度优化到O(mn)。核心原理1. 传统暴力匹配的问题暴力匹配在匹配失败时模式串会回溯到开头主串回溯到起始位置的下一个字符导致大量重复比较。2. KMP的核心思想主串指针不回溯匹配失败时主串的指针i不往回走利用部分匹配信息模式串向右滑动尽可能远的距离前缀函数Partial Match Table预先计算模式串中每个位置的最长相等前后缀长度前缀和后缀核心概念1. 定义前缀从字符串开头开始不包含最后一个字符的所有连续子串后缀从字符串结尾开始不包含第一个字符的所有连续子串真前缀/真后缀不包含整个字符串本身2. 形象比喻 想象一串糖葫芦A B A B C5个山楂text前缀从左边吃 - A 吃第1个 - AB 吃第1-2个 - ABA 吃第1-3个 - ABAB 吃第1-4个 - ❌ 不吃ABABC那是整串 后缀从右边吃 - C 吃最后1个 - BC 吃最后2个 - ABC 吃最后3个 - BABC 吃最后4个 - ❌ 不吃ABABC那是整串3. 具体例子以字符串ABABA为例长度前缀后缀是否相等1AA✅ 相等2ABBA❌ 不相等3ABAABA✅ 相等4ABABBABA❌ 不相等最长相等前后缀长度 3ABA最长相等前后缀对于模式串ABABCA前缀集合{}后缀集合{} → 长度0AB前缀{A}后缀{B} → 长度0ABA前缀{A, AB}后缀{A, BA} → 最长相等前后缀A → 长度1ABAB前缀{A, AB, ABA}后缀{B, AB, BAB} → 最长相等前后缀AB → 长度2ABABC前缀{A, AB, ABA, ABAB}后缀{C, BC, ABC, BABC} → 长度0next数组的含义next[i] 表示模式串前 i1 个字符组成的子串中最长相等前后缀的长度举例模式串 ABABAC位置i子串前缀集合后缀集合最长相等前后缀next[i]0A{}{}无01AB{A}{B}无02ABA{A, AB}{A, BA}A (长度1)13ABAB{A, AB, ABA}{B, AB, BAB}AB (长度2)24ABABA{A, AB, ABA, ABAB}{A, BA, ABA, BABA}ABA (长度3)35ABABAC{A, AB, ABA, ABAB, ABABA}{C, AC, BAC, ABAC, BABAC}无0next数组的多种实现方式方式1经典版前缀表不减一这是最常用的实现next[i]直接存储最长相等前后缀长度。其实寻找的方法跟我们知道的辗转相除法原理有异曲同工之妙。可以抽空对比一下。我们刚学的时候很不理解我们要找的是最大长度相等前后缀这里仅仅比较了某两位位置的字符是否相等很不理解其实这里的门道全在next数组中类似于多米诺骨牌我们前面比较的结果已经被记录在案了影响我们后面的比较看似是两个字符的比较实则已经是动态规划的必然结果了。next[0]0 (基础) ↓ next[1]0 (通过比较s[0]和s[1]) ↓ next[2]1 (通过比较s[0]和s[2]利用next[1]) ↓ next[3]2 (通过比较s[1]和s[3]利用next[2]) ↓ next[4]3 (通过比较s[2]和s[4]利用next[3]) ↓ next[5]0 (通过比较利用next[4]、next[2]、next[0])java /** * 经典版next数组 * next[i] 子串s[0...i]的最长相等前后缀长度 */ public static int[] getNext(String pattern) { int m pattern.length(); int[] next new int[m]; int j 0; // 前缀指针也表示长度 next[0] 0; // 第一个字符没有前后缀 for (int i 1; i m; i) { // 不匹配时回溯 while (j 0 pattern.charAt(j) ! pattern.charAt(i)) { j next[j - 1]; } // 匹配时前进 if (pattern.charAt(j) pattern.charAt(i)) { j; } next[i] j; } return next; }示例运行java String pattern ABABC; int[] next getNext(pattern); // 结果: [0, 0, 1, 2, 0]三、方式2统一减一版next[0] -1这种实现在KMP原论文中使用代码更简洁。java /** * 减一版next数组 * next[i] 最长相等前后缀长度 - 1 */ public static int[] getNextMinusOne(String pattern) { int m pattern.length(); int[] next new int[m]; int j -1; // 前缀指针从-1开始 int i 0; next[0] -1; // 第一个字符设为-1 while (i m - 1) { if (j -1 || pattern.charAt(j) pattern.charAt(i)) { i; j; next[i] j; } else { j next[j]; // 回溯 } } return next; }示例运行java String pattern ABABC; int[] next getNextMinusOne(pattern); // 结果: [-1, 0, 0, 1, 2] // 对应关系经典版1 减一版的值配套的匹配代码java public static int kmpSearchMinusOne(String text, String pattern) { int[] next getNextMinusOne(pattern); int n text.length(), m pattern.length(); int i 0, j 0; while (i n j m) { if (j -1 || text.charAt(i) pattern.charAt(j)) { i; j; } else { j next[j]; } } if (j m) { return i - j; } return -1; }四、方式3优化版nextval解决模式串有大量重复字符时的效率问题。 java /** * 优化版next数组nextval * 避免在重复字符上多次回溯 */ public static int[] getNextVal(String pattern) { int m pattern.length(); int[] nextval new int[m]; int j 0; nextval[0] 0; for (int i 1; i m; i) { while (j 0 pattern.charAt(j) ! pattern.charAt(i)) { j nextval[j - 1]; } if (pattern.charAt(j) pattern.charAt(i)) { j; } // 优化如果下一个字符相同继续回溯 if (i 1 m pattern.charAt(i 1) pattern.charAt(j)) { nextval[i] nextval[j - 1]; } else { nextval[i] j; } } return nextval; }优化效果对比java // 模式串 AAAAA String pattern AAAAA; // 经典版 int[] next1 getNext(pattern); // [0, 1, 2, 3, 4] // 优化版 int[] nextval getNextVal(pattern); // [0, 0, 0, 0, 0] // 优化版避免了重复比较效率更高五、方式4PMT部分匹配表版直接体现部分匹配表的概念。java /** * PMT (Partial Match Table) 版本 * 与经典版相同但命名更学术 */ public static int[] getPMT(String pattern) { int m pattern.length(); int[] pmt new int[m]; int j 0; for (int i 1; i m; i) { while (j 0 pattern.charAt(i) ! pattern.charAt(j)) { j pmt[j - 1]; } if (pattern.charAt(i) pattern.charAt(j)) { j; } pmt[i] j; } return pmt; }图解next数组构建过程以ABABAC为例详细跟踪text初始: pattern A B A B A C 索引: 0 1 2 3 4 5 next: 0 0 0 0 0 0 i1, j0: pattern[1]B vs pattern[0]A → 不匹配 j0, next[1]0 i2, j0: pattern[2]A vs pattern[0]A → 匹配 j1, next[2]1 i3, j1: pattern[3]B vs pattern[1]B → 匹配 j2, next[3]2 i4, j2: pattern[4]A vs pattern[2]A → 匹配 j3, next[4]3 i5, j3: pattern[5]C vs pattern[3]B → 不匹配 jnext[2]1 (回溯) pattern[5]C vs pattern[1]B → 不匹配 jnext[0]0 pattern[5]C vs pattern[0]A → 不匹配 j0, next[5]0 结果: next [0, 0, 1, 2, 3, 0]各版本对比总结版本next[0]特点适用场景经典版本0直观易懂最常用一般场景-1偏移版-1代码简洁判断方便教材、竞赛nextval0优化重复字符特殊模式串PMT0原始定义学术理解使用建议初学者先用经典版本next[0]0竞赛编程用-1偏移版本代码更简洁特殊模式如AAAAA用nextval优化版面试掌握经典版本即可理解原理最重要时间复杂度分析构建next数组O(m)其中m为模式串长度匹配过程O(n)其中n为主串长度总时间复杂度O(m n)空间复杂度O(m)用于存储next数组总结KMP算法的精髓在于避免主串回溯通过分析模式串自身特性确定在不匹配时模式串应该移动的距离前缀函数核心是next数组记录了模式串的前后缀匹配信息空间换时间用O(m)的预处理空间换取O(mn)的匹配时间KMP算法适用于需要多次匹配或模式串较长、主串很大的场景但对于一般场景语言一些内置的find()方法基于Boyer-Moore和Horspool等优化算法通常更快。类比理解以上就是KMO算法的理论基础对于不了解的同学听起来肯定很晦涩难懂。下面我们来形象的理解一下比喻一查字典找单词想象你在查字典找单词APPLE暴力方法笨办法从第一页第一个词开始一个字母一个字母对比发现第3个字母对不上就回到开头从下一页第一个词重新开始就像你每次犯错都要从头翻字典超级慢KMP方法聪明办法你已经知道APP这三个字母是对的下一次查找时直接从P开始继续往后找因为你知道APP后面可能接着LE不需要重新检查已知的部分比喻二开车找路假设你要从A点到B点路线是直行→右转→直行→左转→直行暴力匹配迷路后回到起点text你在路上开到了第4个路口发现走错了 然后掉头开回起点重新开始找路 每次都这样太浪费时间KMP记住经验text你在第4个路口发现错了但你知道 前面3个路口直行→右转→直行是对的 下次你就直接从这个经验点开始不用回到起点题目引入LeetCode28给你两个字符串haystack和needle请你在haystack字符串中找出needle字符串的第一个匹配项的下标下标从 0 开始。如果needle不是haystack的一部分则返回-1。示例 1输入haystack sadbutsad, needle sad输出0解释sad 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 所以返回 0 。示例 2输入haystack leetcode, needle leeto输出-1解释leeto 没有在 leetcode 中出现所以返回 -1 。提示1 haystack.length, needle.length 104haystack和needle仅由小写英文字符组成题目解析这道题是KMP算法的经典应用直接套用KMP匹配过程即可。关键点构建needle的 next 数组用 next 数组指导匹配避免主串指针回溯找到第一个匹配位置后立即返回关于这里的回溯我们可能并不是很能理解我们不知道到底会移到哪里然后就是关于循环中的i和j分别代表什么和初值处理首先strStr方法中的i和j变量全称含义指向iindex of text主串haystack的当前位置正在比较的主串字符jindex of pattern模式串needle的当前位置正在比较的模式串字符然后就是getNext方法中的i和j这里的i是从1开始的因为如果i0此时j也等于0没法比较我们这里的目的是找到字符串的最长相等前后缀。方法i的含义i初值原因getNext后缀末尾指针i1至少需要2个字符才能比较前后缀strStr主串指针i0从主串第一个字符开始匹配然后就是关于回溯的过程并不是只有一次所以我们不能用if必须要用whileneedle: A B A B A C 索引: 0 1 2 3 4 5 next: [0, 0, 1, 2, 3, 0] 主串某个字符: X (假设不等于 C, B, A) 回溯路径while j5 → next[4]3 → 检查needle[3]B ≠ X → next[2]1 → 检查needle[1]B ≠ X → next[0]0 → 检查needle[0]A ≠ X → 最终 j0 用if只能走一步 j5 → next[4]3 → 停止j3 但needle[3]B ≠ X错误应该继续回溯到0回溯位置的确定新位置 最长相等前后缀的长度简单的说跳过的就是最长相等前后缀中的前缀部分。因为我们的next数组已经找到了最长相等的前后缀已匹配: [0...k-1] ... [L-k...L-1] └─前缀─┘ └─后缀─┘ 相等 后缀已经和主串比较过肯定匹配 所以前缀也一定和主串的对应部分匹配 因此不需要重新比较前缀部分 直接从前缀的下一个位置开始为什么不能回溯到后缀呢其实也很简单跳到后缀后面需要调整i让i回溯因为有时候还没匹配完主串就没了会丢失已经确认匹配的前缀信息需要重新比较已经匹配过的字符时间复杂度会退化成O(n²)next数组就写完了之后就是比对主串的方法变量含义初始值作用i主串指针0指向主串当前要比较的字符j模式串指针0指向模式串当前要比较的字符nextnext数组预先计算好记录回溯位置主串指针i从0开始逐个遍历主串的每个字符i只增不减永不回溯 然后不匹配的时候就执行上面的回溯逻辑 之后就是常规操作了。疑点分析我们刚学的时候很不理解我们要找的是最大长度相等前后缀这里仅仅比较了某两位位置的字符是否相等很不理解其实这里的门道全在next数组中类似于多米诺骨牌我们前面比较的结果已经被记录在案了影响我们后面的比较看似是两个字符的比较实则已经是动态规划的必然结果了。next[0]0 (基础) ↓ next[1]0 (通过比较s[0]和s[1]) ↓ next[2]1 (通过比较s[0]和s[2]利用next[1]) ↓ next[3]2 (通过比较s[1]和s[3]利用next[2]) ↓ next[4]3 (通过比较s[2]和s[4]利用next[3]) ↓ next[5]0 (通过比较利用next[4]、next[2]、next[0])表面只比较两个字符但next数组已经记住了之前所有字符的相等关系所以一个字符的比较就能推断出整个前后缀的相等性这是动态规划的思想用小问题的解构建大问题的解题目答案class Solution { //前缀表不减一Java实现 public int strStr(String haystack, String needle) { if (needle.length() 0) return 0; int[] next new int[needle.length()]; getNext(next, needle); int j 0; for (int i 0; i haystack.length(); i) { while (j 0 needle.charAt(j) ! haystack.charAt(i)) j next[j - 1]; if (needle.charAt(j) haystack.charAt(i)) j; if (j needle.length()) return i - needle.length() 1; } return -1; } private void getNext(int[] next, String s) { int j 0; next[0] 0; for (int i 1; i s.length(); i) { while (j 0 s.charAt(j) ! s.charAt(i)) j next[j - 1]; if (s.charAt(j) s.charAt(i)) j; next[i] j; } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励