1. 项目概述从一道408真题说起最近在带学生复习数据结构特别是备战计算机专业基础综合考试也就是大家常说的408的同学几乎每个人都会在KMP算法这一块卡壳。而卡壳的核心往往不是算法思想本身而是那个让人又爱又恨的Next数组以及它的进阶版Nextval数组。尤其是看到类似“求模式串ababaaababaa的Next数组和Nextval数组”这样的题目时很多人的第一反应是头皮发麻只能硬背公式结果下次题目稍微一变又不会了。这其实非常可惜。KMP算法作为字符串匹配领域的里程碑其核心思想——利用已匹配的信息避免主串指针回溯——是非常精妙的。而Next数组正是这一思想的“预计算”产物它决定了当匹配失败时模式串应该向右滑动多远。Nextval则是对Next数组的优化进一步减少了不必要的比较。弄懂它们的求法不仅是为了应付考试里那十来分更是为了真正理解这种“空间换时间”的经典设计模式这种思想在动态规划、状态机等众多领域都有体现。我自己当年考研和后来在项目中做文本搜索引擎、日志分析工具时都深刻体会到KMP及其变种算法的实用性。今天我就以一个老程序员和过来人的身份把Next和Nextval数组的求取问题掰开了、揉碎了讲清楚。我们不搞花架子就用手算的方式一步步推导让你看到每一个数字是怎么来的背后的逻辑是什么。目标是看完这篇文章你能独立、正确、快速地求解任何模式串的这两个数组并且真正理解为什么这么做。2. 核心概念与前置知识梳理在动手计算之前我们必须统一“语言”和“规则”。市面上关于Next数组的定义有细微差别这直接导致了计算结果的不同。为了和408考研的主流教材如王道、天勤以及真题标准答案对齐我们采用以下定义这也是最容易理解、最不易出错的一种。模式串Pattern String我们要在主串中寻找的那个字符串。记为P P[1]P[2]...P[m]。注意这里我们从下标1开始计数这是为了和Next数组的下标对齐避免混淆。P[0]通常不使用或用作其他用途。前缀Prefix与后缀Suffix这是理解Next数组的基石。对于一个字符串ababa其前缀有a,ab,aba,abab注意不包括自身ababa。其后缀有a,ba,aba,baba同样不包括自身ababa。最长公共前后缀Longest Proper Prefix which is also Suffix顾名思义找一个字符串的所有前缀和后缀中最长的那个相等的部分。对于ababa其前缀集合和后缀集合的交集中最长的是aba长度为3。Next[j]数组的定义当模式串中第j个字符P[j]与主串对应字符失配时模式串指针j应该回溯到的新位置。其值为P[1]...P[j-1]这个子串的最长公共前后缀的长度 1。特殊规定Next[1] 0。这表示如果第一个字符就失配那么模式串整体右移一位主串指针前进一位从模式串头重新开始匹配j回溯到0但代码中会1等效于从1开始。另一种等价的感性理解Next[j]是模式串在j位置“失败”后其前缀可以“对齐”到的新位置这个位置之前的部分已经和主串匹配过了无需再比较。Nextval[j]数组的定义在Next[j]的基础上进行的优化。如果回溯后的新位置P[Next[j]]的字符与当前失配字符P[j]相同那么这次回溯后的比较也注定会失败。因此我们可以“递归地”向前寻找直到找到一个字符不同的位置或者到0。Nextval[j]就是优化后的回溯位置。重要提示有些资料如严蔚敏版教材的Next数组定义是“最长公共前后缀的长度”其值比我们这里的定义少1。在解题时务必先明确题目采用的是哪种定义。408考试通常采用我们本文所述的“回溯位置”定义。看清题目要求是避免低级错误的第一步。3. Next数组的手工求法详解与实战理论说再多不如动手算一遍。我们以模式串P ababaaababaa为例这是408真题和众多习题中的常客。我们一步一步推导它的Next数组。我们的目标是求出一个数组Next[1..12]串长m12。记住核心Next[j]等于P[1..j-1]子串的最长公共前后缀长度 1。步骤1初始化Next[1] 0。这是规定表示第一个字符失配模式串右移从0开始代码中会1。步骤2求Next[2]子串是P[1..1] a。该子串的前缀集合空集因为不包括自身长度为1的子串没有真前缀。该子串的后缀集合空集。最长公共前后缀长度 0。因此Next[2] 0 1 1。理解当第二个字符b失配时看前面一个字符a。“a”的前后缀最大匹配长度为0所以回溯到位置011即从模式串的第一个字符a开始重新与主串当前字符比较。步骤3求Next[3]子串是P[1..2] ab。前缀a。后缀b。公共部分无。最长公共前后缀长度 0。因此Next[3] 0 1 1。步骤4求Next[4]子串是P[1..3] aba。前缀a,ab。后缀a,ba。公共部分a。最长公共前后缀长度 1“a”的长度。因此Next[4] 1 1 2。理解当第四个字符b失配时看前面三个字符aba。“aba”有公共前后缀“a”长度为1。这意味着模式串的前1位“a”和后1位“a”是相同的。所以我们可以把模式串的前缀“a”滑动到刚才后缀“a”的位置即从模式串的第2个字符开始比较。步骤5求Next[5]子串是P[1..4] abab。前缀a,ab,aba。后缀b,ab,bab。公共部分ab。最长公共前后缀长度 2。因此Next[5] 2 1 3。步骤6求Next[6]子串是P[1..5] ababa。前缀a,ab,aba,abab。后缀a,ba,aba,baba。公共部分aba长度3。注意“a”也存在但不是最长的。最长公共前后缀长度 3。因此Next[6] 3 1 4。步骤7求Next[7]子串是P[1..6] ababaa。前缀a,ab,aba,abab,ababa。后缀a,aa,baa,abaa,babaa。公共部分只有a。最长公共前后缀长度 1。因此Next[7] 1 1 2。步骤8求Next[8]子串是P[1..7] ababaaa。前缀a,ab,aba,abab,ababa,ababaa。后缀a,aa,aaa,baaa,abaaa,babaaa。公共部分a。最长公共前后缀长度 1。因此Next[8] 1 1 2。步骤9求Next[9]子串是P[1..8] ababaaab。前缀a,ab,aba,abab,ababa,ababaa,ababaaa。后缀b,ab,aab,aaab,baaab,abaaab,babaaab。公共部分ab。最长公共前后缀长度 2。因此Next[9] 2 1 3。步骤10求Next[10]子串是P[1..9] ababaaaba。前缀a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab。后缀a,ba,aba,aaba,aaaba,baaaba,abaaaba,babaaaba。公共部分aba。最长公共前后缀长度 3。因此Next[10] 3 1 4。步骤11求Next[11]子串是P[1..10] ababaaabab。前缀a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab,ababaaaba。后缀b,ab,bab,abab,aabab,aaabab,baaabab,abaaabab,babaaabab。公共部分abab。最长公共前后缀长度 4。因此Next[11] 4 1 5。步骤12求Next[12]子串是P[1..11] ababaaababa。前缀a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab,ababaaaba,ababaaabab。后缀a,ba,aba,baba,ababa,aababa,aaababa,baaababa,abaaababa,babaaababa。公共部分ababa。最长公共前后缀长度 5。因此Next[12] 5 1 6。至此我们得到完整的Next数组j123456789101112P[j]ababaaababaaNext[j]011234223456实操心得手工计算时最容易出错的地方在于找最长公共前后缀。一个技巧是从可能的最长长度子串长度-1开始尝试依次递减。例如对于“abab”先看长度3的前缀“aba”和后缀“bab”是否相等不等。再看长度2的前缀“ab”和后缀“ab”是否相等相等那么长度就是2。这个方法比枚举所有前后缀更高效。4. Nextval数组的优化原理与递推求法有了Next数组Nextval数组的求解就有了基础。Nextval优化的动机非常直接避免明知会失败的比较。考虑这个场景模式串P aaaaab假设我们已经算出其Next数组部分当j5字符a失配时Next[5]4即回溯到j4字符a进行比较。但P[5]和P[4]都是‘a’。既然在j5时和主串的‘x’非a比较失败了那么回溯到j4与同一个主串字符‘x’比较因为P[4] ‘a’所以这次比较也必然失败。这次回溯和比较就是无效的。Nextval的思想就是如果P[j] P[Next[j]]那么Nextval[j]应该等于Nextval[Next[j]]。这是一个递归或递推的过程直到找到某个位置k使得P[j] ! P[k]或者k0。Nextval数组的递推求法规则Nextval[1] 0。第一个字符失配没有优化空间只能从头再来。对于j 1如果P[j] ! P[Next[j]]则Nextval[j] Next[j]。因为回溯后的字符不同这次回溯是“安全”的可能成功。如果P[j] P[Next[j]]则Nextval[j] Nextval[Next[j]]。因为回溯后字符相同必然失败所以直接采用更早位置Next[j]位置优化后的回溯值。我们用刚才求得的P ababaaababaa和它的Next数组来求Nextval。步骤1初始化Nextval[1] 0。步骤2求Nextval[2]j2,P[2]‘b’,Next[2]1,P[1]‘a’。判断P[2] (‘b’) ! P[Next[2]] (P[1]‘a’)。因此Nextval[2] Next[2] 1。步骤3求Nextval[3]j3,P[3]‘a’,Next[3]1,P[1]‘a’。判断P[3] (‘a’) P[Next[3]] (P[1]‘a’)。因此Nextval[3] Nextval[Next[3]] Nextval[1] 0。步骤4求Nextval[4]j4,P[4]‘b’,Next[4]2,P[2]‘b’。判断P[4] (‘b’) P[Next[4]] (P[2]‘b’)。因此Nextval[4] Nextval[Next[4]] Nextval[2] 1。步骤5求Nextval[5]j5,P[5]‘a’,Next[5]3,P[3]‘a’。判断P[5] (‘a’) P[Next[5]] (P[3]‘a’)。因此Nextval[5] Nextval[Next[5]] Nextval[3] 0。步骤6求Nextval[6]j6,P[6]‘a’,Next[6]4,P[4]‘b’。判断P[6] (‘a’) ! P[Next[6]] (P[4]‘b’)。因此Nextval[6] Next[6] 4。步骤7求Nextval[7]j7,P[7]‘a’,Next[7]2,P[2]‘b’。判断P[7] (‘a’) ! P[Next[7]] (P[2]‘b’)。因此Nextval[7] Next[7] 2。步骤8求Nextval[8]j8,P[8]‘b’,Next[8]2,P[2]‘b’。判断P[8] (‘b’) P[Next[8]] (P[2]‘b’)。因此Nextval[8] Nextval[Next[8]] Nextval[2] 1。步骤9求Nextval[9]j9,P[9]‘a’,Next[9]3,P[3]‘a’。判断P[9] (‘a’) P[Next[9]] (P[3]‘a’)。因此Nextval[9] Nextval[Next[9]] Nextval[3] 0。步骤10求Nextval[10]j10,P[10]‘b’,Next[10]4,P[4]‘b’。判断P[10] (‘b’) P[Next[10]] (P[4]‘b’)。因此Nextval[10] Nextval[Next[10]] Nextval[4] 1。步骤11求Nextval[11]j11,P[11]‘a’,Next[11]5,P[5]‘a’。判断P[11] (‘a’) P[Next[11]] (P[5]‘a’)。因此Nextval[11] Nextval[Next[11]] Nextval[5] 0。步骤12求Nextval[12]j12,P[12]‘a’,Next[12]6,P[6]‘a’。判断P[12] (‘a’) P[Next[12]] (P[6]‘a’)。因此Nextval[12] Nextval[Next[12]] Nextval[6] 4。最终我们得到完整的Nextval数组j123456789101112P[j]ababaaababaaNext[j]011234223456Nextval[j]010104210104对比Next和Nextval可以发现很多位置的值被优化得更小了如3-0 2-1 5-0 6-4。这意味着在KMP匹配过程中发生失配时模式串指针j可以回溯得更远跳过更多必然失败的比较从而提升效率。注意事项计算Nextval时必须按顺序从j1到jm递推因为Nextval[j]可能依赖于Nextval[Next[j]]而Next[j]是小于j的。所以只要按顺序算依赖的值总是已经计算好的。5. 代码实现与算法逻辑验证理解了手工计算过程我们来看看代码如何实现。这不仅能验证我们手算的正确性更是为了理解KMP算法是如何利用这两个数组的。这里给出C语言的实现清晰且贴近考试要求。#include stdio.h #include string.h // 生成Next数组 void getNext(char pattern[], int next[], int len) { int i 1, j 0; // i是模式串指针j是前后缀长度指针/回溯位置 next[1] 0; // 初始化 while (i len) { if (j 0 || pattern[i] pattern[j]) { // 如果j为0意味着从头开始匹配或者当前字符相等 i; j; next[i] j; // 记录Next值 } else { // 失配j回溯 j next[j]; } } } // 生成Nextval数组 (基于Next数组优化) void getNextval(char pattern[], int next[], int nextval[], int len) { nextval[1] 0; // 初始化 for (int j 2; j len; j) { if (pattern[j] pattern[next[j]]) { // 如果回溯后的字符与当前字符相同则进一步优化 nextval[j] nextval[next[j]]; } else { // 否则优化后的位置就是Next数组的位置 nextval[j] next[j]; } } } // 打印数组方便调试 void printArray(char* name, int arr[], int len) { printf(%s: [, name); for (int i 1; i len; i) { printf(%d, arr[i]); if (i len) printf(, ); } printf(]\n); } int main() { // 模式串我们使用下标从1开始所以数组0位置空出或放串长度 char P[] ababaaababaa; // 前面加一个空格使得P[1]a int m strlen(P) - 1; // 减去开头的空格 int next[m1]; // 多分配一个方便从1开始索引 int nextval[m1]; getNext(P, next, m); getNextval(P, next, nextval, m); printf(模式串: %s\n, P1); // 从P[1]开始打印 printArray(Next, next, m); printArray(Nextval, nextval, m); // 验证手工计算的结果 int expected_next[] {0, 0, 1, 1, 2, 3, 4, 2, 2, 3, 4, 5, 6}; // 下标0无用 int expected_nextval[] {0, 0, 1, 0, 1, 0, 4, 2, 1, 0, 1, 0, 4}; printf(\n验证结果:\n); int correct 1; for (int i 1; i m; i) { if (next[i] ! expected_next[i]) { printf(Next[%d] 错误: 计算值%d, 期望值%d\n, i, next[i], expected_next[i]); correct 0; } if (nextval[i] ! expected_nextval[i]) { printf(Nextval[%d] 错误: 计算值%d, 期望值%d\n, i, nextval[i], expected_nextval[i]); correct 0; } } if (correct) { printf(恭喜计算结果与手工推导完全一致\n); } return 0; }这段代码的关键在于getNext函数中的while循环。它巧妙地用两个指针i和j在模式串上移动i指向当前正在计算Next值的位置的后一个字符可以理解为后缀的末尾j指向前缀的末尾同时也是Next[i]的候选值。当P[i] P[j]时最长公共前后缀长度可以增加失配时j就利用已经计算好的Next[j]进行回溯。这个算法的时间复杂度是 O(m)非常高效。运行这段代码输出结果会与我们手工计算的结果完全一致这证明了我们推导过程的正确性。实操心得在代码实现时下标处理是新手最容易出错的地方。务必统一约定是让数组下标从0开始还是从1开始我们的示例选择了从1开始这样Next数组的下标和字符位置直观对应。如果你习惯从0开始那么Next[0]-1也是一种常见写法其含义是“第一个字符失配时模式串右移一位且主串指针后移”。无论哪种原理相通但推导出的数值会差1。在考试答题时一定要明确写出你的下标起始约定。6. 常见错误、疑难辨析与速查表即使理解了原理在实际做题和编码中依然会碰到一些典型的“坑”。这里我总结了几类最常见的问题和疑惑点。1. 下标起始问题导致的数值差异这是最大的混乱来源。主要有两种流派王道/天勤/408主流派本文采用字符从P[1]开始存储Next[1]0。Next[j]表示失配时j应跳转到的位置。严蔚敏教材/部分代码实现派字符从P[0]开始存储Next[0]-1。此时Next[j]的值在数值上等于“最长公共前后缀长度”而不是跳转位置。跳转位置需要做j Next[j]操作。应对策略拿到题目首先看它给出的示例或定义。如果题目说“当匹配失败时模式串向右滑动至…”通常采用跳转位置定义本文。如果直接给出一个Next数组值可以尝试用简单字符串如“abab”验证一下属于哪种。2. 求最长公共前后缀时漏掉“真”前缀/后缀公共前后缀必须是真前缀和真后缀即不能是字符串本身。例如求“a”的公共前后缀时前缀集合和后缀集合都是空集长度为0而不是1。这是定义问题必须严格遵守。3. Nextval计算中的递归优化理解不透Nextval的优化是递归的。当P[j] P[Next[j]]时Nextval[j]不是简单等于Next[j]-1之类的而是等于Nextval[Next[j]]。这意味着可能连续优化多次。例如在P“aaaaa”中Next[5]4, 因为P[5]P[4], 所以Nextval[5]Nextval[4]而Next[4]3, 且P[4]P[3], 所以Nextval[4]Nextval[3]……最终Nextval[5]Nextval[1]0。这个过程在手工计算时要一步步递推不能跳步。4. 手工计算速度慢容易乱对于长字符串枚举所有前后缀确实繁琐。可以采用“递推法”口算Next数组这更接近代码逻辑Next[1]0假设已知Next[j]k。求Next[j1]若P[j] P[k]则Next[j1] k1。若P[j] ! P[k]则令k Next[k]继续比较直到k0或相等。用这个方法重新计算“ababaaababaa”的Next数组会快很多且不易错。Nextval则在Next的基础上按规则优化即可。为了帮助大家快速自查我整理了以下速查表问题现象可能原因解决方案计算出的Next数组和答案差1下标定义混淆0起始 vs 1起始明确题目要求统一使用一种定义从头算起。求最长公共前后缀时得到错误长度包含了字符串本身作为前后缀牢记“真”前缀/后缀排除字符串本身。Nextval值优化后比Next还大逻辑错误检查规则只有相等时才优化且优化值是Nextval[Next[j]]这个值一定不大于Next[j]。代码死循环或结果异常数组下标越界或循环条件错误调试时打印每一步的i, j, next[i]值对照手工计算过程逐步排查。对Next[1]0或Next[0]-1的意义不理解对失配处理逻辑不清理解这表示第一个字符就失配时模式串无法利用已匹配信息只能整体右移一位主串指针后移从模式串头重新开始。7. 在KMP算法中的应用与性能对比最后我们来看看Next和Nextval数组是如何被KMP算法使用的并直观感受一下Nextval带来的优化效果。KMP匹配算法核心伪代码使用Next数组int KMP(char text[], char pattern[], int next[]) { int i 1, j 1; // i为主串指针j为模式串指针 int n strlen(text)-1, m strlen(pattern)-1; // 假设下标从1开始 while (i n j m) { if (j 0 || text[i] pattern[j]) { // 匹配成功或j0即模式串第一个字符就失配需要整体右移 i; j; } else { // 失配模式串指针j回溯 j next[j]; } } if (j m) { return i - m; // 匹配成功返回起始位置 } else { return 0; // 匹配失败 } }将上述代码中的next数组替换为nextval数组就是优化后的KMP算法。性能对比实例 假设主串T aaabaaaab模式串P aaaab。先计算Next数组:[0, 1, 2, 3, 4](下标1-5)。再计算Nextval数组:[0, 0, 0, 0, 4]。现在模拟匹配过程使用Next数组T[1]a匹配P[1]a。T[2]a匹配P[2]a。T[3]a匹配P[3]a。T[4]b失配P[4]a。j4回溯到Next[4]3。T[4]b比较P[3]a失配。j3回溯到Next[3]2。T[4]b比较P[2]a失配。j2回溯到Next[2]1。T[4]b比较P[1]a失配。j1回溯到Next[1]0触发j0条件i, j。T[5]a匹配P[1]a... (后续省略) 可以看到在T[4]这个位置因为Next数组的“阶梯式”回溯进行了多次第4、5、6、7步必然失败的比较因为回溯后的字符都是a而主串是b。使用Nextval数组T[1]a匹配P[1]a。T[2]a匹配P[2]a。T[3]a匹配P[3]a。T[4]b失配P[4]a。j4回溯到Nextval[4]0触发j0条件i, j。T[5]a匹配P[1]a... (后续省略) 优化后在T[4]失配时直接一步回溯到0跳过了所有中间必然失败的步骤效率显著提升。对于模式串中有很多连续重复字符的情况Nextval的优化效果极其明显。在实际的文本编辑器、IDE的查找功能或者grep这类命令行工具中使用的往往是优化后的KMP或其变种。理解并掌握Next和Nextval数组你就掌握了KMP算法的灵魂。下次再遇到408真题或者面试官问起字符串匹配你完全可以自信地从原理讲到实现从基础Next讲到优化Nextval把这十分稳稳地拿到手。 KMP算法核心：Next与Nextval数组手工计算与优化原理详解
1. 项目概述从一道408真题说起最近在带学生复习数据结构特别是备战计算机专业基础综合考试也就是大家常说的408的同学几乎每个人都会在KMP算法这一块卡壳。而卡壳的核心往往不是算法思想本身而是那个让人又爱又恨的Next数组以及它的进阶版Nextval数组。尤其是看到类似“求模式串ababaaababaa的Next数组和Nextval数组”这样的题目时很多人的第一反应是头皮发麻只能硬背公式结果下次题目稍微一变又不会了。这其实非常可惜。KMP算法作为字符串匹配领域的里程碑其核心思想——利用已匹配的信息避免主串指针回溯——是非常精妙的。而Next数组正是这一思想的“预计算”产物它决定了当匹配失败时模式串应该向右滑动多远。Nextval则是对Next数组的优化进一步减少了不必要的比较。弄懂它们的求法不仅是为了应付考试里那十来分更是为了真正理解这种“空间换时间”的经典设计模式这种思想在动态规划、状态机等众多领域都有体现。我自己当年考研和后来在项目中做文本搜索引擎、日志分析工具时都深刻体会到KMP及其变种算法的实用性。今天我就以一个老程序员和过来人的身份把Next和Nextval数组的求取问题掰开了、揉碎了讲清楚。我们不搞花架子就用手算的方式一步步推导让你看到每一个数字是怎么来的背后的逻辑是什么。目标是看完这篇文章你能独立、正确、快速地求解任何模式串的这两个数组并且真正理解为什么这么做。2. 核心概念与前置知识梳理在动手计算之前我们必须统一“语言”和“规则”。市面上关于Next数组的定义有细微差别这直接导致了计算结果的不同。为了和408考研的主流教材如王道、天勤以及真题标准答案对齐我们采用以下定义这也是最容易理解、最不易出错的一种。模式串Pattern String我们要在主串中寻找的那个字符串。记为P P[1]P[2]...P[m]。注意这里我们从下标1开始计数这是为了和Next数组的下标对齐避免混淆。P[0]通常不使用或用作其他用途。前缀Prefix与后缀Suffix这是理解Next数组的基石。对于一个字符串ababa其前缀有a,ab,aba,abab注意不包括自身ababa。其后缀有a,ba,aba,baba同样不包括自身ababa。最长公共前后缀Longest Proper Prefix which is also Suffix顾名思义找一个字符串的所有前缀和后缀中最长的那个相等的部分。对于ababa其前缀集合和后缀集合的交集中最长的是aba长度为3。Next[j]数组的定义当模式串中第j个字符P[j]与主串对应字符失配时模式串指针j应该回溯到的新位置。其值为P[1]...P[j-1]这个子串的最长公共前后缀的长度 1。特殊规定Next[1] 0。这表示如果第一个字符就失配那么模式串整体右移一位主串指针前进一位从模式串头重新开始匹配j回溯到0但代码中会1等效于从1开始。另一种等价的感性理解Next[j]是模式串在j位置“失败”后其前缀可以“对齐”到的新位置这个位置之前的部分已经和主串匹配过了无需再比较。Nextval[j]数组的定义在Next[j]的基础上进行的优化。如果回溯后的新位置P[Next[j]]的字符与当前失配字符P[j]相同那么这次回溯后的比较也注定会失败。因此我们可以“递归地”向前寻找直到找到一个字符不同的位置或者到0。Nextval[j]就是优化后的回溯位置。重要提示有些资料如严蔚敏版教材的Next数组定义是“最长公共前后缀的长度”其值比我们这里的定义少1。在解题时务必先明确题目采用的是哪种定义。408考试通常采用我们本文所述的“回溯位置”定义。看清题目要求是避免低级错误的第一步。3. Next数组的手工求法详解与实战理论说再多不如动手算一遍。我们以模式串P ababaaababaa为例这是408真题和众多习题中的常客。我们一步一步推导它的Next数组。我们的目标是求出一个数组Next[1..12]串长m12。记住核心Next[j]等于P[1..j-1]子串的最长公共前后缀长度 1。步骤1初始化Next[1] 0。这是规定表示第一个字符失配模式串右移从0开始代码中会1。步骤2求Next[2]子串是P[1..1] a。该子串的前缀集合空集因为不包括自身长度为1的子串没有真前缀。该子串的后缀集合空集。最长公共前后缀长度 0。因此Next[2] 0 1 1。理解当第二个字符b失配时看前面一个字符a。“a”的前后缀最大匹配长度为0所以回溯到位置011即从模式串的第一个字符a开始重新与主串当前字符比较。步骤3求Next[3]子串是P[1..2] ab。前缀a。后缀b。公共部分无。最长公共前后缀长度 0。因此Next[3] 0 1 1。步骤4求Next[4]子串是P[1..3] aba。前缀a,ab。后缀a,ba。公共部分a。最长公共前后缀长度 1“a”的长度。因此Next[4] 1 1 2。理解当第四个字符b失配时看前面三个字符aba。“aba”有公共前后缀“a”长度为1。这意味着模式串的前1位“a”和后1位“a”是相同的。所以我们可以把模式串的前缀“a”滑动到刚才后缀“a”的位置即从模式串的第2个字符开始比较。步骤5求Next[5]子串是P[1..4] abab。前缀a,ab,aba。后缀b,ab,bab。公共部分ab。最长公共前后缀长度 2。因此Next[5] 2 1 3。步骤6求Next[6]子串是P[1..5] ababa。前缀a,ab,aba,abab。后缀a,ba,aba,baba。公共部分aba长度3。注意“a”也存在但不是最长的。最长公共前后缀长度 3。因此Next[6] 3 1 4。步骤7求Next[7]子串是P[1..6] ababaa。前缀a,ab,aba,abab,ababa。后缀a,aa,baa,abaa,babaa。公共部分只有a。最长公共前后缀长度 1。因此Next[7] 1 1 2。步骤8求Next[8]子串是P[1..7] ababaaa。前缀a,ab,aba,abab,ababa,ababaa。后缀a,aa,aaa,baaa,abaaa,babaaa。公共部分a。最长公共前后缀长度 1。因此Next[8] 1 1 2。步骤9求Next[9]子串是P[1..8] ababaaab。前缀a,ab,aba,abab,ababa,ababaa,ababaaa。后缀b,ab,aab,aaab,baaab,abaaab,babaaab。公共部分ab。最长公共前后缀长度 2。因此Next[9] 2 1 3。步骤10求Next[10]子串是P[1..9] ababaaaba。前缀a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab。后缀a,ba,aba,aaba,aaaba,baaaba,abaaaba,babaaaba。公共部分aba。最长公共前后缀长度 3。因此Next[10] 3 1 4。步骤11求Next[11]子串是P[1..10] ababaaabab。前缀a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab,ababaaaba。后缀b,ab,bab,abab,aabab,aaabab,baaabab,abaaabab,babaaabab。公共部分abab。最长公共前后缀长度 4。因此Next[11] 4 1 5。步骤12求Next[12]子串是P[1..11] ababaaababa。前缀a,ab,aba,abab,ababa,ababaa,ababaaa,ababaaab,ababaaaba,ababaaabab。后缀a,ba,aba,baba,ababa,aababa,aaababa,baaababa,abaaababa,babaaababa。公共部分ababa。最长公共前后缀长度 5。因此Next[12] 5 1 6。至此我们得到完整的Next数组j123456789101112P[j]ababaaababaaNext[j]011234223456实操心得手工计算时最容易出错的地方在于找最长公共前后缀。一个技巧是从可能的最长长度子串长度-1开始尝试依次递减。例如对于“abab”先看长度3的前缀“aba”和后缀“bab”是否相等不等。再看长度2的前缀“ab”和后缀“ab”是否相等相等那么长度就是2。这个方法比枚举所有前后缀更高效。4. Nextval数组的优化原理与递推求法有了Next数组Nextval数组的求解就有了基础。Nextval优化的动机非常直接避免明知会失败的比较。考虑这个场景模式串P aaaaab假设我们已经算出其Next数组部分当j5字符a失配时Next[5]4即回溯到j4字符a进行比较。但P[5]和P[4]都是‘a’。既然在j5时和主串的‘x’非a比较失败了那么回溯到j4与同一个主串字符‘x’比较因为P[4] ‘a’所以这次比较也必然失败。这次回溯和比较就是无效的。Nextval的思想就是如果P[j] P[Next[j]]那么Nextval[j]应该等于Nextval[Next[j]]。这是一个递归或递推的过程直到找到某个位置k使得P[j] ! P[k]或者k0。Nextval数组的递推求法规则Nextval[1] 0。第一个字符失配没有优化空间只能从头再来。对于j 1如果P[j] ! P[Next[j]]则Nextval[j] Next[j]。因为回溯后的字符不同这次回溯是“安全”的可能成功。如果P[j] P[Next[j]]则Nextval[j] Nextval[Next[j]]。因为回溯后字符相同必然失败所以直接采用更早位置Next[j]位置优化后的回溯值。我们用刚才求得的P ababaaababaa和它的Next数组来求Nextval。步骤1初始化Nextval[1] 0。步骤2求Nextval[2]j2,P[2]‘b’,Next[2]1,P[1]‘a’。判断P[2] (‘b’) ! P[Next[2]] (P[1]‘a’)。因此Nextval[2] Next[2] 1。步骤3求Nextval[3]j3,P[3]‘a’,Next[3]1,P[1]‘a’。判断P[3] (‘a’) P[Next[3]] (P[1]‘a’)。因此Nextval[3] Nextval[Next[3]] Nextval[1] 0。步骤4求Nextval[4]j4,P[4]‘b’,Next[4]2,P[2]‘b’。判断P[4] (‘b’) P[Next[4]] (P[2]‘b’)。因此Nextval[4] Nextval[Next[4]] Nextval[2] 1。步骤5求Nextval[5]j5,P[5]‘a’,Next[5]3,P[3]‘a’。判断P[5] (‘a’) P[Next[5]] (P[3]‘a’)。因此Nextval[5] Nextval[Next[5]] Nextval[3] 0。步骤6求Nextval[6]j6,P[6]‘a’,Next[6]4,P[4]‘b’。判断P[6] (‘a’) ! P[Next[6]] (P[4]‘b’)。因此Nextval[6] Next[6] 4。步骤7求Nextval[7]j7,P[7]‘a’,Next[7]2,P[2]‘b’。判断P[7] (‘a’) ! P[Next[7]] (P[2]‘b’)。因此Nextval[7] Next[7] 2。步骤8求Nextval[8]j8,P[8]‘b’,Next[8]2,P[2]‘b’。判断P[8] (‘b’) P[Next[8]] (P[2]‘b’)。因此Nextval[8] Nextval[Next[8]] Nextval[2] 1。步骤9求Nextval[9]j9,P[9]‘a’,Next[9]3,P[3]‘a’。判断P[9] (‘a’) P[Next[9]] (P[3]‘a’)。因此Nextval[9] Nextval[Next[9]] Nextval[3] 0。步骤10求Nextval[10]j10,P[10]‘b’,Next[10]4,P[4]‘b’。判断P[10] (‘b’) P[Next[10]] (P[4]‘b’)。因此Nextval[10] Nextval[Next[10]] Nextval[4] 1。步骤11求Nextval[11]j11,P[11]‘a’,Next[11]5,P[5]‘a’。判断P[11] (‘a’) P[Next[11]] (P[5]‘a’)。因此Nextval[11] Nextval[Next[11]] Nextval[5] 0。步骤12求Nextval[12]j12,P[12]‘a’,Next[12]6,P[6]‘a’。判断P[12] (‘a’) P[Next[12]] (P[6]‘a’)。因此Nextval[12] Nextval[Next[12]] Nextval[6] 4。最终我们得到完整的Nextval数组j123456789101112P[j]ababaaababaaNext[j]011234223456Nextval[j]010104210104对比Next和Nextval可以发现很多位置的值被优化得更小了如3-0 2-1 5-0 6-4。这意味着在KMP匹配过程中发生失配时模式串指针j可以回溯得更远跳过更多必然失败的比较从而提升效率。注意事项计算Nextval时必须按顺序从j1到jm递推因为Nextval[j]可能依赖于Nextval[Next[j]]而Next[j]是小于j的。所以只要按顺序算依赖的值总是已经计算好的。5. 代码实现与算法逻辑验证理解了手工计算过程我们来看看代码如何实现。这不仅能验证我们手算的正确性更是为了理解KMP算法是如何利用这两个数组的。这里给出C语言的实现清晰且贴近考试要求。#include stdio.h #include string.h // 生成Next数组 void getNext(char pattern[], int next[], int len) { int i 1, j 0; // i是模式串指针j是前后缀长度指针/回溯位置 next[1] 0; // 初始化 while (i len) { if (j 0 || pattern[i] pattern[j]) { // 如果j为0意味着从头开始匹配或者当前字符相等 i; j; next[i] j; // 记录Next值 } else { // 失配j回溯 j next[j]; } } } // 生成Nextval数组 (基于Next数组优化) void getNextval(char pattern[], int next[], int nextval[], int len) { nextval[1] 0; // 初始化 for (int j 2; j len; j) { if (pattern[j] pattern[next[j]]) { // 如果回溯后的字符与当前字符相同则进一步优化 nextval[j] nextval[next[j]]; } else { // 否则优化后的位置就是Next数组的位置 nextval[j] next[j]; } } } // 打印数组方便调试 void printArray(char* name, int arr[], int len) { printf(%s: [, name); for (int i 1; i len; i) { printf(%d, arr[i]); if (i len) printf(, ); } printf(]\n); } int main() { // 模式串我们使用下标从1开始所以数组0位置空出或放串长度 char P[] ababaaababaa; // 前面加一个空格使得P[1]a int m strlen(P) - 1; // 减去开头的空格 int next[m1]; // 多分配一个方便从1开始索引 int nextval[m1]; getNext(P, next, m); getNextval(P, next, nextval, m); printf(模式串: %s\n, P1); // 从P[1]开始打印 printArray(Next, next, m); printArray(Nextval, nextval, m); // 验证手工计算的结果 int expected_next[] {0, 0, 1, 1, 2, 3, 4, 2, 2, 3, 4, 5, 6}; // 下标0无用 int expected_nextval[] {0, 0, 1, 0, 1, 0, 4, 2, 1, 0, 1, 0, 4}; printf(\n验证结果:\n); int correct 1; for (int i 1; i m; i) { if (next[i] ! expected_next[i]) { printf(Next[%d] 错误: 计算值%d, 期望值%d\n, i, next[i], expected_next[i]); correct 0; } if (nextval[i] ! expected_nextval[i]) { printf(Nextval[%d] 错误: 计算值%d, 期望值%d\n, i, nextval[i], expected_nextval[i]); correct 0; } } if (correct) { printf(恭喜计算结果与手工推导完全一致\n); } return 0; }这段代码的关键在于getNext函数中的while循环。它巧妙地用两个指针i和j在模式串上移动i指向当前正在计算Next值的位置的后一个字符可以理解为后缀的末尾j指向前缀的末尾同时也是Next[i]的候选值。当P[i] P[j]时最长公共前后缀长度可以增加失配时j就利用已经计算好的Next[j]进行回溯。这个算法的时间复杂度是 O(m)非常高效。运行这段代码输出结果会与我们手工计算的结果完全一致这证明了我们推导过程的正确性。实操心得在代码实现时下标处理是新手最容易出错的地方。务必统一约定是让数组下标从0开始还是从1开始我们的示例选择了从1开始这样Next数组的下标和字符位置直观对应。如果你习惯从0开始那么Next[0]-1也是一种常见写法其含义是“第一个字符失配时模式串右移一位且主串指针后移”。无论哪种原理相通但推导出的数值会差1。在考试答题时一定要明确写出你的下标起始约定。6. 常见错误、疑难辨析与速查表即使理解了原理在实际做题和编码中依然会碰到一些典型的“坑”。这里我总结了几类最常见的问题和疑惑点。1. 下标起始问题导致的数值差异这是最大的混乱来源。主要有两种流派王道/天勤/408主流派本文采用字符从P[1]开始存储Next[1]0。Next[j]表示失配时j应跳转到的位置。严蔚敏教材/部分代码实现派字符从P[0]开始存储Next[0]-1。此时Next[j]的值在数值上等于“最长公共前后缀长度”而不是跳转位置。跳转位置需要做j Next[j]操作。应对策略拿到题目首先看它给出的示例或定义。如果题目说“当匹配失败时模式串向右滑动至…”通常采用跳转位置定义本文。如果直接给出一个Next数组值可以尝试用简单字符串如“abab”验证一下属于哪种。2. 求最长公共前后缀时漏掉“真”前缀/后缀公共前后缀必须是真前缀和真后缀即不能是字符串本身。例如求“a”的公共前后缀时前缀集合和后缀集合都是空集长度为0而不是1。这是定义问题必须严格遵守。3. Nextval计算中的递归优化理解不透Nextval的优化是递归的。当P[j] P[Next[j]]时Nextval[j]不是简单等于Next[j]-1之类的而是等于Nextval[Next[j]]。这意味着可能连续优化多次。例如在P“aaaaa”中Next[5]4, 因为P[5]P[4], 所以Nextval[5]Nextval[4]而Next[4]3, 且P[4]P[3], 所以Nextval[4]Nextval[3]……最终Nextval[5]Nextval[1]0。这个过程在手工计算时要一步步递推不能跳步。4. 手工计算速度慢容易乱对于长字符串枚举所有前后缀确实繁琐。可以采用“递推法”口算Next数组这更接近代码逻辑Next[1]0假设已知Next[j]k。求Next[j1]若P[j] P[k]则Next[j1] k1。若P[j] ! P[k]则令k Next[k]继续比较直到k0或相等。用这个方法重新计算“ababaaababaa”的Next数组会快很多且不易错。Nextval则在Next的基础上按规则优化即可。为了帮助大家快速自查我整理了以下速查表问题现象可能原因解决方案计算出的Next数组和答案差1下标定义混淆0起始 vs 1起始明确题目要求统一使用一种定义从头算起。求最长公共前后缀时得到错误长度包含了字符串本身作为前后缀牢记“真”前缀/后缀排除字符串本身。Nextval值优化后比Next还大逻辑错误检查规则只有相等时才优化且优化值是Nextval[Next[j]]这个值一定不大于Next[j]。代码死循环或结果异常数组下标越界或循环条件错误调试时打印每一步的i, j, next[i]值对照手工计算过程逐步排查。对Next[1]0或Next[0]-1的意义不理解对失配处理逻辑不清理解这表示第一个字符就失配时模式串无法利用已匹配信息只能整体右移一位主串指针后移从模式串头重新开始。7. 在KMP算法中的应用与性能对比最后我们来看看Next和Nextval数组是如何被KMP算法使用的并直观感受一下Nextval带来的优化效果。KMP匹配算法核心伪代码使用Next数组int KMP(char text[], char pattern[], int next[]) { int i 1, j 1; // i为主串指针j为模式串指针 int n strlen(text)-1, m strlen(pattern)-1; // 假设下标从1开始 while (i n j m) { if (j 0 || text[i] pattern[j]) { // 匹配成功或j0即模式串第一个字符就失配需要整体右移 i; j; } else { // 失配模式串指针j回溯 j next[j]; } } if (j m) { return i - m; // 匹配成功返回起始位置 } else { return 0; // 匹配失败 } }将上述代码中的next数组替换为nextval数组就是优化后的KMP算法。性能对比实例 假设主串T aaabaaaab模式串P aaaab。先计算Next数组:[0, 1, 2, 3, 4](下标1-5)。再计算Nextval数组:[0, 0, 0, 0, 4]。现在模拟匹配过程使用Next数组T[1]a匹配P[1]a。T[2]a匹配P[2]a。T[3]a匹配P[3]a。T[4]b失配P[4]a。j4回溯到Next[4]3。T[4]b比较P[3]a失配。j3回溯到Next[3]2。T[4]b比较P[2]a失配。j2回溯到Next[2]1。T[4]b比较P[1]a失配。j1回溯到Next[1]0触发j0条件i, j。T[5]a匹配P[1]a... (后续省略) 可以看到在T[4]这个位置因为Next数组的“阶梯式”回溯进行了多次第4、5、6、7步必然失败的比较因为回溯后的字符都是a而主串是b。使用Nextval数组T[1]a匹配P[1]a。T[2]a匹配P[2]a。T[3]a匹配P[3]a。T[4]b失配P[4]a。j4回溯到Nextval[4]0触发j0条件i, j。T[5]a匹配P[1]a... (后续省略) 优化后在T[4]失配时直接一步回溯到0跳过了所有中间必然失败的步骤效率显著提升。对于模式串中有很多连续重复字符的情况Nextval的优化效果极其明显。在实际的文本编辑器、IDE的查找功能或者grep这类命令行工具中使用的往往是优化后的KMP或其变种。理解并掌握Next和Nextval数组你就掌握了KMP算法的灵魂。下次再遇到408真题或者面试官问起字符串匹配你完全可以自信地从原理讲到实现从基础Next讲到优化Nextval把这十分稳稳地拿到手。