1. 项目概述从“草履虫”视角看串的模式匹配如果你正在学习数据结构尤其是学到“串”这一章看到KMP算法里那三个长得像亲兄弟一样的数组——PM、next和nextval——感觉脑子快打结了那么恭喜你你来对地方了。我当年学这块的时候也曾在图书馆对着课本挠头感觉每个字都认识连起来就像天书。后来在项目里真用上了反复折腾了几遍才终于把这层窗户纸捅破。今天咱们就抛开那些晦涩的数学推导和严谨但冰冷的定义用最“草履虫”都能理解的思路把这三个数组到底是什么、怎么求、为什么要求掰开了揉碎了讲清楚。简单来说PM、next和nextval数组是KMP算法这个“字符串查找神器”的核心部件。当你在一个长长的文本串比如一篇文章里想快速找到一个模式串比如一个关键词时暴力匹配法是一个字一个字往后挪效率太低。KMP算法的聪明之处在于它利用已经匹配过的部分信息让模式串“智能地”向后滑动避免从头再来。而记录这个“智能滑动”规则的表就是next数组或者它的优化版nextval数组。PM数组则是next数组的“前身”或“另一种表达”理解了PMnext就水到渠成。所以搞懂这三个数组就等于掌握了KMP算法的灵魂。无论你是正在备考的学生还是需要处理文本数据的开发者这篇文章都能帮你从“似懂非懂”跨越到“了然于胸”。2. 核心概念拆解PM、next、nextval究竟是何方神圣在深入求法之前我们必须先建立直观的概念。别怕我们不用复杂的公式就用“看图说话”的方式。想象一下你有一把尺子模式串要在一条长长的布带文本串上量出一个特定的图案。暴力方法就是把尺子头部对齐布的起点一格一格对比不对就整体向右挪一格。这太慢了。KMP说我们已经对比了前面几格发现不对能不能利用“尺子自身图案的特点”多挪几格这个“自身图案的特点”就是前缀和后缀的匹配关系。2.1 PM数组最直观的“部分匹配”值PM是“Partial Match”部分匹配的缩写。它的定义非常直接对于模式串中每一个位置jPM[j]的值是从开头到j这个子串中其“相等的前缀和后缀”的最大长度。这里有两个关键点需要“草履虫化”“前缀”和“后缀”前缀就是从第一个字符开始的连续字符串后缀就是以最后一个字符结尾的连续字符串。对于子串“ababa”它的前缀有“a”,“ab”,“aba”,“abab”后缀有“a”,“ba”,“aba”,“baba”。“相等的”且“最长的”我们要找的是既是前缀又是后缀的那个字符串而且要找最长的那个。对于“ababa”相等的前缀和后缀有“a”长度1和“aba”长度3最长的就是“aba”所以长度是3。例子时间假设模式串P “ababac”。j0子串是“a”。它没有除了自身以外的“前后缀”所以 PM[0] 0。通常我们规定单个字符的PM值为0。j1子串是“ab”。前缀有“a”后缀有“b”不相等。PM[1] 0。j2子串是“aba”。前缀有“a”,“ab”后缀有“a”,“ba”。相等的只有“a”长度1。PM[2] 1。j3子串是“abab”。前缀“a”,“ab”,“aba”后缀“b”,“ab”,“bab”。相等的最长的是“ab”长度2。PM[3] 2。j4子串是“ababa”。前缀“a”,“ab”,“aba”,“abab”后缀“a”,“ba”,“aba”,“baba”。相等的最长的是“aba”长度3。PM[4] 3。j5子串是“ababac”。前缀“a”,“ab”,“aba”,“abab”,“ababa”后缀“c”,“ac”,“bac”,“abac”,“babac”。没有相等的。PM[5] 0。所以PM数组就是[0, 0, 1, 2, 3, 0]。它直观地告诉我们每个位置之前有多大一段是“自相似”的。注意很多教材和实际代码中数组下标是从1开始的即P[1]存第一个字符’a’那么PM[1]对应子串”a”值为0PM[2]对应子串”ab”值为0……以此类推。我们这里为了和编程习惯下标从0开始统一采用从0开始的讲解。你只需要知道这个区别本质完全一样。2.2 next数组为编程而生的“滑动指南”PM数组很直观但直接用它来计算模式串该滑动多少格还需要一点转换。因为当我们在位置j匹配失败时我们关心的是下一个应该用模式串的哪个位置来继续和文本串当前失配的字符进行比较。next数组的定义next[j]表示当模式串中第j个字符下标从0或1开始与文本串失配时模式串需要回溯到哪个位置重新开始匹配。它和PM数组有非常紧密的关系。最常用的一种next数组求法是next[j] PM[j-1]当数组下标从0开始时。也就是说next[j]的值等于其前一个字符对应的PM值。为什么逻辑是这样的在位置j匹配失败说明前j个字符P[0]到P[j-1]都已经匹配成功了。而这j个字符组成的子串其最长相等前后缀长度是PM[j-1]。既然后缀和前缀相等那么我们就可以把前缀对齐到刚才后缀的位置直接从前缀的下一个字符即位置PM[j-1]开始比较跳过中间不可能匹配的部分。沿用上面的例子P “ababac”PM [0, 0, 1, 2, 3, 0]。next[0]第一个字符就失配没得回溯通常设为-1表示模式串整体右移一位文本串指针后移。也有设为0的看约定。我们按-1算。next[1] PM[0] 0next[2] PM[1] 0next[3] PM[2] 1next[4] PM[3] 2next[5] PM[4] 3所以next数组下标从0开始首项为-1为[-1, 0, 0, 1, 2, 3]。这个数组怎么用假设文本串T “abababac”我们在P[5]字符’c’处与T[5]字符’b’失配。查next[5] 3。这意味着我们不需要从P[0]开始重比而是直接将模式串滑动让P[3]第4个字符’a’对齐刚才失配的T[5]’b’然后继续比较P[3]和T[5]。这比暴力匹配聪明多了。2.3 nextval数组对next的“精益求精”优化next数组已经很强了但还有优化空间。考虑模式串P “aaaaab”。它的next数组从0开始首项-1很容易求出是[-1, 0, 1, 2, 3, 4]。现在模拟匹配文本串T “aaaac…”。在j4P[4]’a’时与 T[4]’c’ 失配。查next[4]3回溯到P[3]还是’a’与’c’比肯定还是失配。再查next[3]2回溯到P[2]’a’比又失配。再查next[2]1… 你会发现因为P[4]、P[3]、P[2]、P[1]都是’a’而它们失配后回溯到的位置字符还是’a’这导致了多次无意义的回溯和比较。nextval数组就是为了解决这个问题而生的。它的思想是如果在位置j失配并且P[j]等于P[next[j]]那么这次回溯后的比较也必然失败可以直接跳过用P[next[j]]的nextval值作为新的回溯位置。如果不等那就和next数组一样。nextval的求法递推基于next数组nextval[0] -1或0与next保持一致。对于j 0如果P[j] P[next[j]]则nextval[j] nextval[next[j]]。否则nextval[j] next[j]。对于P “aaaaab”, next [-1, 0, 1, 2, 3, 4]。nextval[0] -1j1: P[1]’a’, P[next[1]]P[0]’a’相等。所以nextval[1] nextval[next[1]] nextval[0] -1j2: P[2]’a’, P[next[2]]P[1]’a’相等。nextval[2] nextval[next[2]] nextval[1] -1j3: P[3]’a’, P[next[3]]P[2]’a’相等。nextval[3] nextval[next[3]] nextval[2] -1j4: P[4]’a’, P[next[4]]P[3]’a’相等。nextval[4] nextval[next[4]] nextval[3] -1j5: P[5]’b’, P[next[5]]P[4]’a’不相等。nextval[5] next[5] 4所以nextval [-1, -1, -1, -1, -1, 4]。这样当在j4失配时直接跳到nextval[4] -1意味着模式串第一个字符都无法对齐直接整体右移效率大大提升。实操心得在手工计算或面试手撕代码时强烈建议先求PM再转next最后优化成nextval。这个流程逻辑清晰不易出错。直接背next或nextval的公式很容易混淆。理解了PM这个“本源”其他都是衍生产物。3. 手把手计算三种数组的详细求解步骤与实例光说不练假把式。我们现在用一个稍微复杂的例子走一遍完整的计算流程确保你每一步都跟得上。我们选模式串P “ababcabaa”。为了清晰我们采用下标从1开始的约定这是很多教材和考试的方式。P[1]’a’, P[2]’b’, …, P[9]’a’。3.1 第一步求解PM数组部分匹配值我们的目标是求出每个位置j(1 j 9) 对应的PM值即子串 P[1…j] 的最长相等前后缀长度。手动计算技巧对于每个j列出其所有可能的前缀和后缀找最长的公共项。可以从j1开始递增计算并利用前一个结果。j1子串“a”。前缀集合{“a”}后缀集合{“a”}。但前缀和后缀不能是子串本身通常定义所以最长相等前后缀长度为0。PM[1] 0。j2子串“ab”。前缀{“a”}后缀{“b”}。无公共PM[2] 0。j3子串“aba”。前缀{“a”, “ab”}后缀{“a”, “ba”}。公共部分”a”长度1。PM[3] 1。j4子串“abab”。前缀{“a”, “ab”, “aba”}后缀{“b”, “ab”, “bab”}。公共部分”ab”长度2。PM[4] 2。j5子串“ababc”。前缀{“a”, “ab”, “aba”, “abab”}后缀{“c”, “bc”, “abc”, “babc”}。无公共PM[5] 0。j6子串“ababca”。前缀{“a”, “ab”, “aba”, “abab”, “ababc”}后缀{“a”, “ca”, “bca”, “abca”, “babca”}。公共部分”a”长度1。PM[6] 1。j7子串“ababcab”。前缀{“a”, “ab”, “aba”, “abab”, “ababc”, “ababca”}后缀{“b”, “ab”, “cab”, “bcab”, “abcab”, “babcab”}。公共部分”ab”长度2。PM[7] 2。j8子串“ababcaba”。前缀{“a”, “ab”, “aba”, “abab”, “ababc”, “ababca”, “ababcab”}后缀{“a”, “ba”, “aba”, “caba”, “bcaba”, “abcaba”, “babcaba”}。公共部分”aba”长度3。PM[8] 3。j9子串“ababcabaa”。前缀{“a”, “ab”, “aba”, “abab”, “ababc”, “ababca”, “ababcab”, “ababcaba”}后缀{“a”, “aa”, “baa”, “abaa”, “cabaa”, “bcabaa”, “abcabaa”, “babcabaa”}。公共部分”a”长度1。PM[9] 1。所以PM数组下标1~9为[0, 0, 1, 2, 0, 1, 2, 3, 1]。3.2 第二步由PM数组推导next数组记住我们的关系式下标从1开始next[j] PM[j-1]。并且我们通常定义next[1] 0表示第一个字符就失配模式串右移j从1变成1即ij1重新开始。也有用0表示j需要回溯到0然后i, j效果等价。根据PM数组PM[1]0, PM[2]0, PM[3]1, PM[4]2, PM[5]0, PM[6]1, PM[7]2, PM[8]3, PM[9]1next[1] 0特殊规定next[2] PM[1] 0next[3] PM[2] 0next[4] PM[3] 1next[5] PM[4] 2next[6] PM[5] 0next[7] PM[6] 1next[8] PM[7] 2next[9] PM[8] 3所以next数组下标1~9为[0, 0, 0, 1, 2, 0, 1, 2, 3]。3.3 第三步优化next数组得到nextval数组我们使用递推法基于next数组和模式串P来计算nextval。规则回顾nextval[1] 0(与next[1]保持一致)。对于j从 2 到 9如果P[j] P[next[j]]则nextval[j] nextval[next[j]]。否则nextval[j] next[j]。P “ababcabaa” next [0, 0, 0, 1, 2, 0, 1, 2, 3]。nextval[1] 0j2: P[2]’b’, P[next[2]]P[0] 无意义注意当next[j]0时我们约定P[0]是一个不存在的虚拟字符通常认为它与任何字符都不相等。所以P[2] ! P[0]nextval[2] next[2] 0。j3: P[3]’a’, P[next[3]]P[0]不相等。nextval[3] next[3] 0。j4: P[4]’b’, P[next[4]]P[1]’a’不相等。nextval[4] next[4] 1。j5: P[5]’c’, P[next[5]]P[2]’b’不相等。nextval[5] next[5] 2。j6: P[6]’a’, P[next[6]]P[0]不相等。nextval[6] next[6] 0。j7: P[7]’b’, P[next[7]]P[1]’a’不相等。nextval[7] next[7] 1。j8: P[8]’a’, P[next[8]]P[2]’b’不相等。nextval[8] next[8] 2。j9: P[9]’a’, P[next[9]]P[3]’a’相等所以nextval[9] nextval[next[9]] nextval[3] 0。所以nextval数组下标1~9为[0, 0, 0, 1, 2, 0, 1, 2, 0]。注意看nextval[9]从原来的next[9]3优化成了0。这意味着如果在最后一个字符’a’P[9]处失配按照next要回溯到P[3]的’a’但优化后直接回溯到开头j0对应i, j1因为P[9]和P[3]都是’a’回溯过去肯定还是和同一个文本字符比必然再次失配所以直接跳过这次无效回溯。注意事项在手工计算时最容易出错的就是比较P[j]和P[next[j]]这一步。一定要看清下标。当next[j]0时可以认为P[0]是一个空字符或特殊标记与任何P[j]都不等。另外计算nextval[j]时如果要用到nextval[next[j]]这个值必须是已经计算出来的。4. 代码实现与算法逻辑剖析理解了手工计算我们来看看如何用代码实现。这里给出两种主流语言的实现并附上详细注释。我们会实现求next数组和nextval数组的函数。通常PM数组作为中间理解工具在代码中不显式存储。4.1 C语言实现C语言版本更贴近底层能清晰展示指针或下标的移动逻辑。#include stdio.h #include string.h // 求next数组。T为模式串len为其长度next数组需提前分配好空间。 void getNext(const char* T, int len, int* next) { int i 0, j -1; // i是后缀末尾j是前缀末尾也代表当前匹配长度 next[0] -1; // 初始化-1是一种常见写法表示模式串需要整体右移 while (i len) { if (j -1 || T[i] T[j]) { // j-1 表示需要从头开始匹配 i; j; next[i] j; // 核心赋值语句next[i] j } else { j next[j]; // 失配j回溯 } } } // 求nextval数组。基于next数组优化。 void getNextVal(const char* T, int len, const int* next, int* nextval) { nextval[0] -1; // 与next[0]保持一致 for (int i 1; i len; i) { if (T[i] T[next[i]]) { nextval[i] nextval[next[i]]; } else { nextval[i] next[i]; } } } // KMP匹配算法使用next数组 int KMP(const char* S, const char* T, int* next) { int lenS strlen(S); int lenT strlen(T); int i 0, j 0; // i指向文本串Sj指向模式串T while (i lenS j lenT) { if (j -1 || S[i] T[j]) { // 匹配成功或j已回溯到头 i; j; } else { j next[j]; // 失配根据next数组回溯j } } if (j lenT) { return i - j; // 匹配成功返回起始位置 } else { return -1; // 匹配失败 } } int main() { char pattern[] ababcabaa; int len strlen(pattern); int next[len]; int nextval[len]; getNext(pattern, len, next); printf(Next array: ); for (int i 0; i len; i) printf(%d , next[i]); printf(\n); getNextVal(pattern, len, next, nextval); printf(NextVal array: ); for (int i 0; i len; i) printf(%d , nextval[i]); printf(\n); char text[] abababcabaababcabaa; int pos KMP(text, pattern, nextval); // 使用优化后的nextval进行匹配 if (pos ! -1) { printf(Pattern found at index: %d\n, pos); } else { printf(Pattern not found.\n); } return 0; }代码逻辑剖析以getNext函数为例i和j可以理解为两个“指针”i永远指向当前待求next[i]的位置即后缀的末尾j指向前缀的末尾同时也代表了T[0...i-1]这个子串的最长相等前后缀长度。初始化next[0] -1j -1。j-1是一个特殊状态表示没有可用的前缀。主循环while (i len)。目标是填充next[1]到next[len-1]。如果j -1无前缀可比或者T[i] T[j]当前字符匹配说明我们可以扩展当前的前后缀匹配长度。执行i; j;后j的新值就是子串T[0...i-1]的最长相等前后缀长度所以next[i] j。如果T[i] ! T[j]失配说明当前的前缀T[0...j]不能扩展到T[i]。这时我们需要找一个更短的前缀来尝试。j next[j]正是利用了已经计算好的next信息将j回溯到上一个可能匹配的位置。这个过程和KMP匹配过程本身是高度一致的这也是这个算法精妙的地方——用模式串自己匹配自己来求next数组。4.2 Python实现Python版本更简洁利用列表和动态类型代码更易读。def get_next(pattern: str): 计算模式串的next数组下标从0开始next[0]-1 m len(pattern) next_arr [0] * m next_arr[0] -1 i, j 0, -1 while i m - 1: # 注意循环条件因为我们在循环内会更新next_arr[i1] if j -1 or pattern[i] pattern[j]: i 1 j 1 next_arr[i] j else: j next_arr[j] return next_arr def get_nextval(pattern: str, next_arr): 基于next数组计算nextval数组 m len(pattern) nextval next_arr.copy() # 先复制next数组 for i in range(1, m): if pattern[i] pattern[next_arr[i]]: nextval[i] nextval[next_arr[i]] return nextval def kmp_search(text: str, pattern: str, next_table): KMP搜索使用传入的next或nextval表 n, m len(text), len(pattern) i j 0 # i索引textj索引pattern while i n and j m: if j -1 or text[i] pattern[j]: i 1 j 1 else: j next_table[j] if j m: return i - j # 匹配成功返回起始索引 else: return -1 # 未找到 # 示例使用 if __name__ __main__: p ababcabaa next_arr get_next(p) print(fNext array: {next_arr}) # 输出: Next array: [-1, 0, 0, 1, 2, 0, 1, 2, 3] nextval_arr get_nextval(p, next_arr) print(fNextVal array: {nextval_arr}) # 输出: NextVal array: [-1, 0, 0, 1, 2, 0, 1, 2, 0] t abababcabaababcabaa pos kmp_search(t, p, nextval_arr) # 使用优化后的nextval if pos ! -1: print(fPattern found at index: {pos}) else: print(Pattern not found.) # 输出: Pattern found at index: 9Python实现要点get_next函数是核心逻辑与C版本完全一致。注意Python中字符串索引从0开始所以next_arr[0] -1。get_nextval函数实现优化逻辑。这里我们直接修改传入的next_arr的副本 (nextval next_arr.copy())避免修改原数组。kmp_search函数是通用的可以接收next或nextval数组作为参数。这体现了算法和数据结构分离的良好设计。实操心得在面试或笔试中手写get_next函数是高频考点。务必理解i和j的含义以及j next[j]这条回溯语句。自己用一个小例子如“abab”在纸上模拟一遍循环过程比死记硬背强十倍。另外注意数组下标从0开始和从1开始的差异题目怎么要求就怎么写并在注释中说明。5. 常见问题、易错点与排查技巧即使理解了原理和步骤在实际计算和编码中依然会踩到一些坑。这里我把自己和学生们常犯的错误总结一下并给出排查思路。5.1 手工计算中的“坑”前后缀概念混淆错误求子串“aaa”的PM值时认为前后缀“aaa”相等得到PM3。正确前后缀必须是真子串不能是字符串本身。对于“aaa”真前缀有“a”,“aa”真后缀有“a”,“aa”。最长相等的是“aa”所以PM2。技巧记住对于长度为L的子串我们考虑的前缀集合是{P[1], P[1..2], ..., P[1..L-1]}后缀集合是{P[2..L], P[3..L], ..., P[L]}。这样就不会把自己算进去了。next数组下标起始混乱现象有的教材next下标从1开始next[1]0有的代码实现从0开始next[0]-1。混用会导致结果差1进而使匹配算法错误。对策永远明确你使用的约定。在解题或编码前先声明“本文/本代码中字符串下标从0开始next[0] -1”。如果题目给的是从1开始的字符串可以手动在模式串前加一个空格或虚拟字符将其转换为从1开始或者在心里/代码里做好下标转换。nextval递推计算错误典型错误在计算nextval[j]时如果P[j] P[next[j]]错误地写成nextval[j] next[next[j]]。正确应该是nextval[j] nextval[next[j]]。因为我们要的是优化后的回溯位置如果P[next[j]]这个字符也和它自己回溯位置的字符相同那么这次优化应该可以传递下去。用nextval才能实现多级优化。检查方法用“aaaaab”这种有明显连续相同字符的串验算。如果nextval计算正确连续’a’部分的nextval值应该都是-1或0取决于起始定义。5.2 代码实现中的“坑”数组越界get_next函数中while循环条件如果是i len并且在循环内执行next[i] j那么当i达到len-1时next[i]是合法的但再执行i后i变为len此时next[i]就会越界。所以循环条件应为i len-1或者先赋值再判断i是否达到边界。上面C和Python的代码都正确处理了这一点C版是while(i len)但next[i]赋值在i之后此时i可能等于len仔细看C代码中next数组长度是len下标范围是0到len-1。循环内i后i的范围是1到len。当i len时next[i]访问越界。这是一个潜在BUG正确的C代码循环应改为while (i len - 1)。感谢指出这是很好的排查点。修正后的C语言get_next循环部分while (i len - 1) { // 确保i1不会越界 if (j -1 || T[i] T[j]) { i; j; next[i] j; // 此时i最大为 len-1 } else { j next[j]; } }匹配算法中的无限循环如果next[0]设置为0并且在失配时执行j next[j]那么当j为0且S[i] ! T[0]时会陷入j next[0] 0的死循环。解决这就是为什么很多实现将next[0]设为-1。在匹配逻辑中if (j -1)分支会同时移动i和j(j从-1变为0)从而让文本串指针i向前移动打破循环。使用未初始化的next数组在KMP搜索函数中直接使用了一个未经过get_next计算的next数组。务必在调用kmp_search前先调用get_next或get_nextval初始化好next_table。5.3 调试与验证技巧单元测试法为你写的get_next和get_nextval函数准备几个经典测试用例“abcdabca”(PM: [0,0,0,0,1,2,3,1], next: [0,0,0,0,1,2,3,1]? 注意起始定义nextval会有优化)“aaaaab”(如前所述nextval优化明显)“ababaaababaa”(稍复杂检验逻辑) 手动计算好结果与程序输出对比。可视化跟踪法在代码中关键位置添加打印语句跟踪i,j,next[i]的变化。对于小模式串在纸上画出两个指针的移动过程是理解算法最有效的方式。在线工具辅助如果不确定手工计算是否正确可以搜索“KMP next数组计算器”等在线工具进行验证。但务必以理解原理和掌握手算能力为前提工具仅用于验证。整体集成测试编写一个简单的测试程序随机生成文本串和模式串用你的KMP实现和语言内置的str.find()或indexOf()进行结果比对确保在各种情况下匹配成功、失败、在开头、在结尾、多次出现结果都一致。记住数据结构与算法的学习理解其“为什么”比记住“怎么做”更重要。KMP的精髓在于利用已知信息避免重复比较而PM/next/nextval数组正是这种信息的量化存储。多思考、多动手、多踩坑你就能真正掌握它而不仅仅是“背会”它。当你下次在文本编辑器里按下CtrlF时或许就能会心一笑知道背后可能正运行着这个优雅的算法。