考点频率★★★★★数据结构必考选择题常考next数组的计算下午题偶尔出现难度⭐⭐⭐⭐⭐数据结构中最难理解的内容之一建议重点掌握next数组的推导方法理解KMP如何避免主串指针回溯会手动计算next数组值1️⃣ 什么是串的模式匹配模式匹配是指在主串目标串中查找模式串子串的位置。主串被查找的字符串如ABABCABAB可以理解为“长文本”模式串要查找的字符串如ABAB可以理解为“关键词”生活类比你在Word里按CtrlF搜索一个词Word会在整篇文档主串里找这个词模式串并告诉你它在第几页第几行——这就是模式匹配。2️⃣ 朴素匹配BF算法的痛点朴素匹配Brute-ForceBF是最直接的思路从主串的每个位置开始逐个字符与模式串比较匹配失败就回溯到下一个位置重新开始。主串A B A B C A B A B 模式A B A B第1轮A B A B ✅ 匹配成功这就是为什么它叫“暴力”——它从主串的每个位置都试一遍直到找到匹配或试完所有位置BF的时间复杂度O(n×m)O(n \times m)O(n×m)其中nnn是主串长度mmm是模式串长度。最坏情况下如主串为AAAA...AB模式串为AAAA...AC几乎每个位置都要比较mmm次。BF的痛点每次匹配失败后主串的指针要回溯到开始位置的下一个字符之前比较过的信息全部丢弃导致大量重复比较。3️⃣ KMP算法的核心思想KMP算法Knuth-Morris-Pratt的核心是匹配失败时主串指针不回溯只移动模式串指针。主串指针i只前进不后退模式串指针j根据next数组回退到某个位置继续匹配生活类比你看一本书找一句话。BF算法是每次发现不对就把书合上翻回开头下一页重新看。KMP是你手里夹着一张书签next数组发现不对时书签告诉你“别翻回去从书签标记的那一页接着看就行”——你只往前翻永远不往回翻。KMP的工作流程主串指针i从 0 开始模式串指针j从 0 开始如果主串[i] 模式串[j]ij如果j已经到达模式串末尾 → 匹配成功返回i - j如果主串[i] ! 模式串[j]如果j 0i第一个字符都不匹配主串指针前移一位否则j next[j]模式串指针回退到next[j]主串指针i不动4️⃣ next数组的含义核心next[j]表示当模式串中第j个字符与主串不匹配时模式串指针应该回退到的位置。next数组的值仅取决于模式串本身与主串无关。这意味着对于任意给定的模式串我们只需要事先算好一个固定的next数组就可以在任何主串中使用它来加速匹配——一次计算到处使用。核心理解next[j]是模式串前j个字符中最长相等前后缀的长度。它是一个“真前缀”与“真后缀”的匹配度表示当匹配失败时模式串可以“复用”多少已经比较过的信息。具体含义当模式串的j位置匹配失败时即主串[i] ! 模式串[j]模式串的j指针回退到next[j]继续与主串的当前位置i比较主串指针i不动。5️⃣ 如何手工计算 next 数组5.1 前缀、后缀、最长相等前后缀前缀除最后一个字符外从第一个字符开始的连续子串后缀除第一个字符外到最后一个字符结束的连续子串最长相等前后缀前缀集合和后缀集合的交集中长度最长的那个示例模式串ABAB计算前3个字符ABA的最长相等前后缀。前缀AAB后缀ABA交集A最长相等前后缀长度 15.2 手算 next 数组下标从 0 开始设模式串为P长度为m。next[0] -1第一个字符不匹配时主串指针前移。对于j 1next[j] 模式串P[0..j-1]中最长相等前后缀的长度。模式串j前 j 个字符最长相等前后缀长度next[j]ABAB0---11A002AB003ABA1A1所以next [-1, 0, 0, 1]5.3 另一种常见定义下标从 1 开始考试可能遇到有些教材中next[1] 0next[j] 模式串P[1..j-1]中最长相等前后缀长度 1。这种定义下next数组的值整体比下标从0开始的定义大1。考试中如果遇到看清题目给出的定义方式按照题目给定的定义来计算。6️⃣ KMP算法的匹配过程示例主串ABABCABAB模式串ABABnext[-1, 0, 0, 1]第1轮i0, j0 主串A B A B C A B A B 模式A B A B ↑ 匹配A A ✅ → i1, j1 第2轮i1, j1 主串A B A B C A B A B 模式A B A B ↑ 匹配B B ✅ → i2, j2 第3轮i2, j2 主串A B A B C A B A B 模式A B A B ↑ 匹配A A ✅ → i3, j3 第4轮i3, j3 主串A B A B C A B A B 模式A B A B ↑ 匹配B B ✅ → i4, j4 第5轮j 4模式串长度匹配成功 匹配位置 i - j 4 - 4 0主串中从下标0开始的子串匹配实际上KMP的优势主要体现在匹配失败时。上面的例子匹配过程非常顺利没有触发回退。为了更好地展示KMP的“主串指针不回溯”特点下面换一个更典型的场景场景主串ABABABC模式串ABABC匹配到第5个字符时失败。第1-4轮A B A B 都匹配成功i4, j4 第5轮主串[i] A模式串[j] C → 匹配失败 此时主串指针 i4指向A模式串指针 j4指向C BF做法i 回溯到 1重新从模式串第0位开始比较 → 已比较的信息全丢失 KMP做法查 next[4] 1j 1i 不动仍为4 模式串指针从1开始继续与主串的 i4 位置比较主串指针i没有回溯这就是KMP效率高的根本原因。7️⃣ KMP vs BF 对比对比项BF朴素匹配KMP主串指针匹配失败时回溯永不回溯模式串指针每次都回到0根据next数组回退时间复杂度O(n×m)O(n \times m)O(n×m)O(nm)O(n m)O(nm)额外空间无O(m)O(m)O(m)next数组预处理无需要计算next数组8️⃣ 经典例题例题1模式串ABCDABD的 next 数组下标从0开始为 。解析next[0] -1j1前1个字符A→ 最长相等前后缀长度 0 →next[1] 0j2前2个字符AB→ 最长相等前后缀长度 0 →next[2] 0j3前3个字符ABC→ 最长相等前后缀长度 0 →next[3] 0j4前4个字符ABCD→ 最长相等前后缀长度 0 →next[4] 0j5前5个字符ABCDA→ 前缀A 后缀A→ 长度 1 →next[5] 1j6前6个字符ABCDAB→ 前缀AB 后缀AB→ 长度 2 →next[6] 2答案[-1, 0, 0, 0, 0, 1, 2]例题2已知模式串P ABABCnext 数组为[-1, 0, 0, 1, 2]。当匹配到j4时失配模式串指针应回退到 。A. 0B. 1C. 2D. 3解析next[4] 2回退到 2。选C。例题3判断KMP算法中当匹配失败时主串指针需要回溯到之前的位置重新比较。 解析错误。KMP的核心优势就是主串指针永不回溯只移动模式串指针。9️⃣ 记忆口诀KMP核心不回溯主串指针只前进。next数组看模式最长相等前后缀。next[0] -1next[j]算前 j 个字符的最长相等前后缀长度。匹配失败看 next模式指针跳过去。 小测验评论区对答案模式串AAAB的 next 数组下标从0开始为 。A.[-1, 0, 0, 0]B.[-1, 0, 1, 1]C.[-1, 0, 1, 2]D.[-1, 0, 0, 1]本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #KMP算法 #模式匹配 #数据结构 #软考备考
