1. 从一次调试引发的困惑说起如果你在数据结构课上或者准备考研、面试刷题时认真研究过KMP算法那么你大概率遇到过这个让人挠头的问题为什么我手算的next数组和书上给的例子、或者网上搜到的代码跑出来的结果总是差那么一个“1”更具体地说你可能会发现严蔚敏老师《数据结构C语言版》教材里给出的next数组和李春葆老师《数据结构教程》里的定义以及很多网络博客、开源代码的实现看起来“长得不一样”。我第一次遇到这个问题是在用C实现一个字符串匹配函数时。我严格按照严老师书上的定义和例子推导出了模式串ababaaababaa的next数组为[-1, 0, 0, 1, 2, 3, 1, 1, 2, 3, 4, 5]。信心满满地写进代码一运行匹配结果却错了。调试了半天最后发现网上一个广为流传的KMP实现其next数组是[0, 1, 1, 2, 3, 4, 2, 2, 3, 4, 5, 6]。我的第一反应是“难道我算错了” 但反复核对书上的推导过程逻辑完全自洽。直到我对比了两位老师对next[j]的定义以及这个值在匹配失败时具体如何使用才恍然大悟这根本不是一个对错问题而是两种等价的、但起始下标定义不同的实现约定。这个“差1”的现象是学习KMP算法时一个经典的“坑”。它不涉及算法核心思想即利用已匹配部分的信息避免主串指针回溯的理解偏差纯粹是实现细节上的不同约定导致的表象差异。但恰恰是这个细节如果搞不清楚就会严重阻碍我们真正理解算法的代码实现甚至怀疑自己是否掌握了KMP。今天我们就来彻底拆解这个“差1”之谜让你不仅知其然更知其所以然从此面对任何版本的KMP实现都能从容应对。2. 核心分歧点next[j]到底表示什么要理解为什么会有不同的next数组我们必须回到KMP算法的本质并厘清next数组每一项的确切含义。KMP算法在模式串P的某个位置j匹配失败时不是简单地将模式串整体后移一位、主串指针回溯而是将模式串向右滑动一定距离让模式串的next[j]位置与主串当前失配位置对齐继续进行比较。这里的关键是next[j]的值指示的是当P[j]失配时下一个应该与主串当前字符进行比较的模式串字符的下标。两种主流定义的分歧就源于对这个“下一个比较位置”的设定不同。2.1 严蔚敏版定义next[j]是“最长相等前后缀长度”在严蔚敏老师的《数据结构C语言版》中对next数组的定义非常直接当j 0时即模式串第一个字符就失配next[0] -1。这是一个特殊标志表示模式串需要整体右移一位主串指针前进一位。当j 0时next[j]的值为模式串子串P[0...j-1]即j位置之前的字符串的最长相等前后缀的长度。这里有几个关键点计算范围只考虑j位置之前的子串P[0...j-1]不包括P[j]本身。值的含义这个“长度”直接对应模式串中的一个下标。因为字符串下标从0开始长度为k的前缀是P[0...k-1]所以这个长度值k恰好就是下一个应该比较的字符P[k]的下标。使用方式当在j处失配执行j next[j]。如果next[j] k (k0)那么下一步就是用P[k]去和主串当前字符比较。如果next[j] -1则意味着j被重置为-1循环中通常会紧接着j和i使得模式串从P[0]开始与主串的下一个字符比较。举例模式串P ababj0:next[0] -1(约定)j1: 子串a无真前后缀最长相等前后缀长度为0 next[1] 0j2: 子串ab前缀{“a”}后缀{“b”}不相等长度为0 next[2] 0j3: 子串aba前缀{“a”, “ab”}后缀{“a”, “ba”}相等的最长前后缀是“a”长度为1 next[3] 1所以严版next数组为[-1, 0, 0, 1]2.2 李春葆及其他常见实现版next[j]是“最长相等前后缀长度 1”在李春葆老师的《数据结构教程》以及很多算法导论类书籍、网络教程和实际代码库如许多C标准库std::search的实现思路、Java的String.indexOf优化版本参考的KMP中采用了另一种定义。为了区分我们常称之为next数组但有些资料会命名为fail或lpsLongest Prefix Suffix。其定义如下当j 0时next[0] 0。有时也设为-1但更常见是0。当j 0时next[j]的值为模式串子串P[0...j]即包含j位置在内的字符串的最长相等前后缀的长度。注意这里的区别计算范围考虑的是包含当前位置j在内的子串P[0...j]。值的含义同样是“长度”。但因为计算范围包含了P[j]且这个长度值k指向的是前缀的结束位置的下一个位置或者说是相等后缀之后第一个字符的位置。因此当在j处失配时下一个比较的位置就是P[k]。从数值上看这个k恰好等于“严版定义下的next[j] 1”。举例同样以模式串P abab为例j0: 子串a最长相等前后缀长度为0通常定义自身不算next[0] 0j1: 子串ab最长相等前后缀长度为0 next[1] 0? 这里需要小心。按照“包含j”的定义P[0...1]ab其最长相等真前后缀长度为0。但很多实现为了编程方便会设定next[0]-1然后从j1开始next[1]表示P[0]子串的最长...这反而容易混乱。更清晰且常见的“1”版定义是next[j]表示当P[j] ! T[i]时下一次匹配时模式串的起始比较位置。这个值是通过递推公式求的其物理意义是P[0...next[j]-1] P[j-next[j]1 ... j]。最终效果是next数组的值整体比严版的大1。我们换一个更标准的计算以最终代码输出为目标 对于Pabab许多资料给出的“1”版next数组是[0, 1, 1, 2]。j0:next[0]0(通常固定)j1: 字符a之前无匹配next[1]1? 这里“1”的含义是下一个比较位置是P[1]不对。实际上next[1]通常也是0或1。我们用一个更通用的方法“1”版的next[j]其值等于“严版next[j] 1”。 严版next[-1, 0, 0, 1]各加1 [0, 1, 1, 2]这就是李春葆等版本常见的next数组。2.3 对比表格与本质分析为了更清晰地看到区别我们用一个更长的例子P ababaaababaa来对比下标 j01234567891011字符 P[j]ababaaababaa严版 next[j]-100123112345常见“1”版 next[j]011234223456注意上表中“1”版是一个常见形式实际中可能遇到next[0]-1的“1”版变体但其j0的部分依然满足“严版值1”的规律。本质分析 这两种定义在数学逻辑上是完全等价的就像摄氏温标和华氏温标描述的是同一个温度。差异只源于基准点下标起点的选择不同。严版以-1作为模式串滑动的一个特殊标志next[j]直接表示“跳转后与主串当前字符比较的模式串字符下标”。它的计算基础是j之前的子串。“1”版通常以0作为起点next[j]表示的是“最长相等前后缀的长度”这个长度值在匹配失败时被直接用作下一个比较位置的下标。它的计算基础是包含j的子串或者通过递推公式得到其结果数值上恰好是严版值加1。为什么会有这两种严版的定义与KMP原始论文以及许多早期经典教材如《数据结构》严蔚敏一脉相承概念上非常直观“最长前后缀长度”就是下一个对齐点。“1”版在编程实现上有时更简洁。特别是当使用next数组进行匹配时循环结构可以写得更加统一省去对-1的特殊判断。许多在线评测系统OJ和现代的算法代码示例更倾向于这种。3. 从理论到代码两种定义的实现差异理解了定义我们来看代码实现。两种next数组的求法构造函数和用法匹配函数都有细微差别。3.1 求next数组的代码对比假设模式串存储在数组p[]中长度为m。严蔚敏版 next 数组求法void getNext_yan(const char p[], int m, int next[]) { int j 0, k -1; next[0] -1; // 初始化 while (j m - 1) { // 注意循环条件计算到next[m-1]为止 if (k -1 || p[j] p[k]) { // p[j] 是当前待求next值的字符p[k]是前缀末尾 j; k; // 优化点通常这里会判断p[j]是否等于p[k]若相等则next[j]next[k]即nextval优化 next[j] k; } else { k next[k]; // 失配k回溯 } } }关键点初始化next[0] -1,j0,k-1。循环中j指向当前正在计算next值的位置的后一个位置。所以while (j m - 1)确保计算到jm-1即最后一个字符的next值。p[j] p[k]时next[j1] k1。这里的k1就是最长相等前后缀的长度。常见“1”版 next 数组求法void getNext_plusone(const char p[], int m, int next[]) { int j 0, k -1; // 依然可以用k-1开始 next[0] -1; // 有些实现这里next[0]0但用-1更方便匹配循环 while (j m) { if (k -1 || p[j] p[k]) { j; k; next[j] k; // 注意这里j已经自增所以next[j]对应的是原p[j-1]的“1”版值 } else { k next[k]; } } }或者更直观的“长度”定义版next[0]0void getNext_lps(const char p[], int m, int next[]) { next[0] 0; // 长度为1的子串最长公共前后缀长度为0 int len 0; // 当前最长公共前后缀长度 int i 1; while (i m) { if (p[i] p[len]) { len; next[i] len; i; } else { if (len ! 0) { len next[len - 1]; // 关键回溯利用已计算的next信息 } else { next[i] len; // 即0 i; } } } }关键点第二种写法next[0]0更直观体现了“长度”定义。len记录的就是P[0...i-1]子串的最长公共前后缀长度。回溯时len next[len - 1]是精髓其原理与严版中k next[k]一致但下标需要调整。最终得到的next[i]值就是“1”版的值。例如对于abab得到[0, 0, 1, 2]注意这里next[1]0与之前举例的[0,1,1,2]略有不同这是next[0]初始化为0且计算逻辑细微差别导致的但整体“比严版大1”的趋势不变匹配函数需对应调整。3.2 使用next数组进行匹配的代码对比匹配函数kmpSearch的写法必须与getNext生成的next数组严格配套。配套严版next数组的匹配函数int kmpSearch_yan(const char s[], int n, const char p[], int m, const int next[]) { int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { // j-1 是特殊状态 i; j; } else { j next[j]; // 直接跳转 } } if (j m) { return i - j; // 匹配成功返回起始位置 } return -1; // 未匹配 }特点需要显式判断j -1的情况。当j next[j]导致j-1时意味着模式串无法利用已匹配信息下一轮循环将通过j-1的条件同时移动i和jj从-1变为0实现模式串右移一位。配套“1”版next数组以next[0]0为例的匹配函数int kmpSearch_plusone(const char s[], int n, const char p[], int m, const int next[]) { int i 0, j 0; while (i n j m) { if (j 0 || s[i] p[j]) { // 这里判断j0对应next[0]0的含义 i; j; } else { j next[j]; // 跳转 } } // ... 返回逻辑相同 }或者更常见的与next[0]-1的“1”版数组配套此时匹配函数与严版几乎一样int kmpSearch_plusone_v2(const char s[], int n, const char p[], int m, const int next[]) { int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { // 依然判断j-1 i; j; } else { j next[j]; // 注意这里的next数组值比严版大1但跳转逻辑一致 } } // ... 返回逻辑相同 }核心匹配逻辑是相通的都是通过j next[j]来回溯模式串的指针。区别在于next数组的具体值以及初始状态的处理。只要getNext和kmpSearch使用同一种约定算法就能正确工作。4. 实战中的“坑”与如何选择在实际学习、做题、面试或工程中混淆两种next数组是导致KMP算法“失灵”的最常见原因。4.1 典型踩坑场景“我的代码和教材一样但结果不对”你看了严蔚敏教材的推导手算了next数组然后去LeetCode上找一道字符串匹配的题套用了某个题解给出的KMP模板该模板很可能使用“1”版next自然无法通过。“网上代码片段无法拼接”你从博客A复制了getNext函数从博客B复制了kmpSearch函数两者可能基于不同的next定义合并运行必然出错。“next数组的优化nextval让我更混乱”在next数组基础上为了处理像aaaaab这种字符连续重复的情况还有nextval优化。如果基础next的定义没搞清楚nextval的计算就更是一团浆糊。4.2 如何快速识别与统一当你拿到一段KMP代码或一个next数组时如何快速判断它属于哪一派看next[0]的值如果是-1很可能是严版或兼容严版的“1”版其j0部分值比严版大1。如果是0则一定是“1”版长度版。看next[1]的值对于长度2的模式串严版next[1]永远是0。因为子串P[0]只有一个字符无真前后缀。“1”版next[0]0next[1]可能是0或1取决于具体实现逻辑。看匹配函数中对j-1的判断如果有if (j -1 ...)则它期望的next[0]是-1。如果只判断if (j 0 ...)或没有对j的特殊判断则它期望的next[0]是0。最稳妥的方法不要混用确定一套定义getNext函数和与之配套的匹配逻辑kmpSearch函数并始终如一地使用。在阅读他人代码或教材时先花几分钟分析其next数组的定义和匹配逻辑而不是直接套用数值。4.3 个人建议与选择对于学习者我个人的建议是理解阶段以严蔚敏版为准严版的定义next[j]为P[0...j-1]的最长前后缀长度在概念上最清晰、最直观。它直接体现了KMP的思想利用已经匹配成功的部分信息j之前的部分。先掌握这个对理解算法本质最有帮助。实现与刷题推荐使用“1”版且next[0]-1在编程实现和应对算法竞赛、面试时我推荐使用一种变体即计算出的next数组在数值上等于“严版值1”但同时保持next[0] -1。这样做的优点是匹配函数统一匹配函数可以沿用严版那种判断j -1的简洁形式。计算方便求next数组的代码与严版几乎一致只需在赋值时稍作调整或者直接按严版求然后给每个值加1但next[0]保持-1。兼容性好很多在线代码模板采用这种方式。示例代码推荐实践版// 生成“严版值1但next[0]保持-1”的next数组 void getNext_recommended(const char p[], int m, int next[]) { int j 0, k -1; next[0] -1; while (j m) { if (k -1 || p[j] p[k]) { j; k; // 与严版唯一区别这里直接存储k即“长度”也就是严版值1 next[j] k; // 当jm时这句会写越界实际循环应改为j m-1此处为示意逻辑 } else { k next[k]; } } } // 匹配函数与严版完全一致 int kmpSearch_recommended(...) { // 同 kmpSearch_yan // ... 判断 j -1 }对于模式串abab这个函数得到的next数组是[-1, 0, 1, 2]。你可以验证从下标1开始每个值正好是严版值[0,0,1]加1。这样既保留了-1作为特殊标志的便利又使得next值除0外具有“长度”的直观性。5. 举一反三next数组的优化nextval在彻底理解next数组两种定义后我们才能无困惑地学习它的优化版——nextval数组。nextval的出现是为了解决KMP算法的一个低效角落。考虑模式串P aaaaab主串S aaaaaa...aaaaab前面很多个a。严版next数组[-1, 0, 1, 2, 3, 4]当在P[4]倒数第二个a处与主串的某个字符假设是c失配时根据next[4]3跳转到P[3]还是a比较必然再次失配接着next[3]2... 这样会连续失配多次才退到P[0]。虽然主串指针i不回溯但模式串指针j在反复回溯效率退化。优化思想如果P[j]失配并且P[next[j]] P[j]那么跳转到next[j]位置后与当前主串字符比较的依然是一个相同的字符P[j]必然再次失配。所以我们可以“一步到位”直接跳到P[next[next[j]]]直到P[j] ! P[next[j]]为止。这个优化后的数组就是nextval。nextval的计算基于严版nextvoid getNextVal(const char p[], int m, const int next[], int nextval[]) { nextval[0] -1; // 与next[0]一致 for (int j 1; j m; j) { if (p[j] p[next[j]]) { nextval[j] nextval[next[j]]; // 关键优化失配字符相同则继承更早的跳转位置 } else { nextval[j] next[j]; // 否则与next相同 } } }对于Paaaaab:next:[-1, 0, 1, 2, 3, 4]nextval:[-1, -1, -1, -1, -1, 4]解释P[1]a,P[next[1]]P[0]a相等所以nextval[1] nextval[next[1]] nextval[0] -1。同理nextval[2]也等于-1... 直到P[5]b,P[next[5]]P[4]a不相等所以nextval[5] next[5] 4。这样当在任何一个a位置失配时都会直接跳转到-1然后主串和模式串指针同时后移避免了无效的多次回溯。重要提示nextval的优化是建立在next数组基础上的。你必须先明确你的next数组是哪种定义然后在此基础上计算nextval。不同的next基础定义会导致计算nextval时判断条件p[j] p[next[j]]中的next[j]取值不同最终得到的nextval数组也不同。但优化逻辑和最终达到的效果避免相同字符连续失配是一致的。6. 总结与终极记忆技巧“李春葆、严蔚敏关于KMP算法的next数组值差1”这个问题本质上是对同一算法两种不同实现约定的观察。它们就像同一把尺子一个从0开始刻度一个从1开始刻度量出的长度数值差1但描述的物体实际长度是一样的。为了永远不再混淆你可以记住以下三点抓住核心不变式无论哪种定义KMP的核心思想不变——利用已匹配部分的最大公共前后缀信息避免主串指针回溯。next数组的核心作用是在失配时告诉模式串指针j应该回退到哪个位置继续比较。实现时自洽选择一套定义求next的函数和与之配套的匹配逻辑并坚持使用。在阅读、调试、整合他人代码时第一件事就是验证这两者是否配套。推荐实践路径初学理解用严蔚敏版定义next[j]是P[0...j-1]的最长前后缀长度next[0]-1。实际编码刷题可采用**“严版值1且next[0]-1”**的兼容方案这样匹配函数写法最简洁通用。最后判断你是否真正搞懂了这个问题可以尝试这个测试对于模式串abcabd分别写出严版和“1”版next[0]0的next数组并写出配套的getNext函数和kmpSearch函数片段。如果你能清晰地写出来并且理解每一行代码为什么这样写那么恭喜你这个“差1”的坑你已经彻底跨过去了。