1. 项目概述一个困扰无数初学者的经典“坑点”如果你正在学习数据结构与算法尤其是字符串匹配这个章节那么“KMP算法”绝对是一个绕不开的名字。而提到KMP那个神秘的next数组就成了理解它的关键也是无数人包括当年的我第一次感到“怀疑人生”的地方。更让人头疼的是你会发现不同教材、不同博客、甚至不同老师的代码里next数组的取值竟然不一样有的从0开始有的从-1开始有的值整体相差1。这其中国内最经典的两位作者——严蔚敏老师和李春葆老师的教材关于next数组的定义差异堪称是数据结构学习路上的“经典悬案”。我最初学的是严蔚敏老师的《数据结构C语言版》书上那个从1开始计数的next数组让我琢磨了好久。后来参考李春葆老师的习题集发现他的next数组值好像总比严版的小1当时就懵了心想“到底哪个是对的我写的代码怎么调都通不过是不是教材印错了” 相信有这个困惑的朋友不在少数。今天我们就来彻底扒开这个“差1”问题的本质。这不仅仅是一个数字游戏背后涉及到对KMP算法核心思想——“前缀等于后缀”这一模式串自匹配过程——两种不同但都合理的实现逻辑。理解它你才算真正看透了KMP而不是死记硬背一个模板。本文将带你从零开始手把手推导两种next数组并用最直白的语言和可运行的代码示例解释为什么会有差异以及如何根据不同的next数组写出正确的匹配代码。无论你是正在备考期末、准备复试还是单纯想攻克这个算法难点这篇文章都将为你提供一份清晰的“避坑指南”。2. 核心思想拆解KMP与next数组的本质在深入“差1”问题之前我们必须夯实基础明白KMP算法到底在解决什么以及next数组为何而生。2.1 暴力匹配的瓶颈与KMP的智慧假设我们有一个主串S “ABCDABABCDABD”和一个模式串P “ABCDABD”。最朴素的暴力匹配Brute-Force算法就是让模式串从主串的第一个字符开始对齐逐个比较。一旦发现不匹配模式串就整体向右滑动一位再从头开始比较。主串 S: ABCDABABCDABD 模式串P: ABCDABD ^ 第7位‘A’和‘D’不匹配暴力法的做法是P: ABCDABD S: ABCDABABCDABD ^ 滑动一位P的‘A’和S的‘B’对齐重新开始你会发现在第一次匹配失败时我们已经知道了主串中前六个字符是“ABCDAB”。暴力法无视了这个已知信息把模式串移到了已知不可能匹配的位置‘B’和‘A’做了大量无谓的比较。KMP算法的核心智慧就在于利用已经部分匹配这个有效信息保持主串指针i不回溯通过修改模式串的指针j让模式串尽可能地“滑动”到有效的位置继续比较。这个“有效的位置”就是通过next数组告诉我们的。2.2 next数组的使命记录“前缀等于后缀”的最大长度next数组是针对模式串P预先计算出来的一个表。对于模式串P的每一个位置j0 j len(P)next[j]的值含义是当模式串中第j个字符与主串失配时下一步应该用模式串的第next[j]个字符去与主串的当前字符进行比较。那么next[j]具体怎么定呢这就引出了KMP最精髓的概念最长相等前后缀。前缀指除了最后一个字符以外一个字符串的全部头部组合。后缀指除了第一个字符以外一个字符串的全部尾部组合。对于模式串P在位置j之前的子串P[0...j-1]我们找出其最长的、相等的前缀和后缀的长度这个长度值就是next[j]定义的基础。以模式串“ABCDABD”为例我们手动计算一下我们先按一种直观的方式j0子串为空没有前后缀长度记为0。j1子串“A”前缀集合{空}后缀集合{空}最长相等前后缀长度为0。j2子串“AB”前缀{“A”}后缀{“B”}无相等长度为0。j3子串“ABC”前缀{“A”, “AB”}后缀{“BC”, “C”}无相等长度为0。j4子串“ABCD”前缀{“A”, “AB”, “ABC”}后缀{“BCD”, “CD”, “D”}无相等长度为0。j5子串“ABCDA”前缀{“A”, “AB”, “ABC”, “ABCD”}后缀{“BCDA”, “CDA”, “DA”, “A”}。发现前缀“A”和后缀“A”相等长度为1。j6子串“ABCDAB”前缀{“A”, “AB”, “ABC”, “ABCD”, “ABCDA”}后缀{“BCDAB”, “CDAB”, “DAB”, “AB”, “B”}。发现前缀“AB”和后缀“AB”相等长度为2。如果我们把这个“最长相等前后缀长度”直接作为next[j]的值那么对于“ABCDABD”我们得到的数组是[0, 0, 0, 0, 0, 1, 2]。这是一种定义方式。注意这里有一个极其关键的细节我们计算的是子串P[0...j-1]的最长相等前后缀长度这个长度值本身指示的是前缀的结束位置的下一个索引因为长度是从1开始数的而索引是从0开始的。这个“索引”与“长度”之间的微妙关系正是后续一切差异的根源。3. 两种next数组的详细解析与对比现在让我们正式引入严蔚敏版和李春葆版代表两种主流流派的next数组。它们的区别核心在于数组的起始索引和值的含义。为了清晰我们统一用模式串P “ababaaababaa”来演示。这是一个前后缀结构更丰富的例子更能说明问题。3.1 严蔚敏版next数组通常称为next数组在严蔚敏老师的教材中以清华大学出版社的《数据结构C语言版》为例书中的字符串通常采用从1开始计数的存储方式即P[1]存第一个字符。在这种约定下next数组的定义是next[1] 0。这是一个固定的初始化值表示第一个字符失配时模式串需要整体右移一位主串指针前进对于j 1next[j]的值为当模式串中第j个字符与主串失配时下一次匹配时模式串应回溯到的位置k。这个k满足P[1...k-1] P[j-k1...j-1]且k是满足此条件即“前缀等于后缀”的最大值。如果不存在这样的k则next[j]1。通俗理解在严版定义下next[j]的值直接就是下一次匹配时模式串指针j应该跳转到的位置索引。这个位置是从1开始数的。手工计算严版 模式串P: a b a b a a a b a b a a (索引从1开始)j1:next[1] 0。 (规定)j2: 子串“a”最长相等前后缀长度为0。但根据定义我们要找回溯位置k。长度为0意味着没有相等前后缀所以下一次应该从模式串开头比较即k1。所以next[2] 1。j3: 子串“ab”最长相等前后缀长度为0。next[3] 1。j4: 子串“aba”最长相等前后缀是“a”长度为1。长度为1意味着前缀“a”和后缀“a”相等。这个前缀“a”对应的是P[1]它的下一个位置是k2。所以next[4] 2。因为用P[2]去接着比j5: 子串“abab”最长相等前后缀是“ab”长度为2。前缀“ab”对应P[1]~P[2]下一个位置k3。next[5] 3。j6: 子串“ababa”最长相等前后缀是“aba”长度为3。next[6] 4。j7: 子串“ababaa”最长相等前后缀是“a”长度为1。next[7] 2。... 以此类推。最终得到的严版next数组为[0, 1, 1, 2, 3, 4, 2, ...](索引从1开始)。关键点严版的next[j]值 最长相等前后缀长度 1。因为长度指示的是相等部分的字符数而我们要跳转到的位置是相等前缀的下一个字符的索引。3.2 李春葆版/主流实现版next数组通常称为next数组或部分匹配表在李春葆老师的教材以及绝大多数编程实现如LeetCode题解、算法导论中字符串采用从0开始计数的C/C/Java/Python标准方式。在这种约定下next数组通常有两种极其相似的定义定义A直接使用最长公共前后缀长度next[0] -1。一个特殊的哨兵值表示模式串第一个字符就失配主串指针i后移模式串指针j无法再回溯重置为0对于j 0next[j]的值为子串P[0...j-1]的最长相等前后缀的长度。定义B优化版有时称nextval在定义A的基础上进行优化。如果回溯后的字符P[next[j]]与当前失配字符P[j]相同那么这次回溯是无效的可以递归地向前回溯。即next[j] next[next[j]]。我们通常讨论的基础next数组指的是定义A。手工计算李版/主流版-定义A 模式串P: a b a b a a a b a b a a (索引从0开始)j0:next[0] -1。 (规定)j1: 子串“a”(P[0])最长相等前后缀长度为0。next[1] 0。j2: 子串“ab”(P[0~1])长度为0。next[2] 0。j3: 子串“aba”(P[0~2])最长相等前后缀“a”长度为1。next[3] 1。j4: 子串“abab”(P[0~3])最长相等前后缀“ab”长度为2。next[4] 2。j5: 子串“ababa”(P[0~4])最长相等前后缀“aba”长度为3。next[5] 3。j6: 子串“ababaa”(P[0~5])最长相等前后缀“a”长度为1。next[6] 1。... 以此类推。最终得到的李版定义Anext数组为[-1, 0, 0, 1, 2, 3, 1, ...](索引从0开始)。关键点李版的next[j]值 最长相等前后缀长度。它指示的是相等前缀的最后一个字符的索引因为索引从0开始长度-1就是最后一个字符的索引。当发生失配时我们让j next[j]意思是让模式串的j指针回退到前缀的后面准备用P[j]此时j是前缀后的第一个字符去和主串比较。如果next[j] -1则意味着主串当前字符不可能与模式串的任何前缀匹配主串指针i后移j重置为0。3.3 “差1”关系的本质与对照表现在我们可以清晰地看到“差1”现象的本质索引起点不同严版从1开始李版从0开始。这直接导致了数组下标的不同。值的含义不同严版值最长相等前后缀长度 1。它直接指向下一次比较时模式串的字符位置。李版值最长相等前后缀长度。它指向已匹配前缀的末尾位置或者说是回溯后待比较字符的前一个位置。如果我们忽略索引起点的差异只关注值的序列会发现一个规律严版next数组的值从j2开始 李版next数组对应位置的值 1让我们用“ababaaababaa”的前几个值来验证将严版索引视为从1开始李版索引视为从0开始位置 (j)子串 P[0...j-1]最长相等前后缀长度严版 next[j] (长度1)李版 next[j] (长度)1“a”0102“ab”0103“aba”1214“abab”2325“ababa”3436“ababaa”121实操心得很多同学在手动计算next数组时容易晕根本原因是没有严格区分“长度”和“索引”这两个概念。我建议固定使用一种理解方式。对于编程实现强烈建议采用从0开始索引、next[j]等于最长公共前后缀长度的定义即李春葆/主流版。因为这个定义更直接地反映了算法的数学本质且与大多数编程语言的字符串索引方式天然契合。你只需要记住next[j]告诉你当P[j]失配时已匹配部分P[0...j-1]中有多长的前缀是可以直接“复用”的接下来应该用P[next[j]]去和主串比较当next[j] 0时。4. 两种next数组的代码实现与匹配过程理解了定义我们来看看代码怎么写以及匹配过程如何随之调整。这是将理论转化为可运行程序的关键一步也是很多人在实现时出错的地方。4.1 计算next数组的算法实现无论是哪种定义计算next数组的核心算法都是基于模式串本身的匹配这是一个动态规划的过程。我们以主流的从0索引定义李版为例讲解最经典的求解算法。算法思想假设我们已经知道了next[0], next[1], ..., next[j]现在要求next[j1]。设k next[j]。如果P[j] P[k]那么P[0...k]就是P[0...j]的最长相等前后缀因为P[0...k-1]已经是P[0...j-1]的最长相等前后缀了现在末尾字符也相等。所以next[j1] k 1。如果P[j] ! P[k]说明在P[0...j]中长度为k1的前后缀不相等。那么我们就需要找一个更短的相等前后缀。下一个可能的前缀结束位置在哪里就在next[k]所指示的位置因为next[k]的含义就是P[0...k-1]的最长相等前后缀长度。我们令k next[k]然后继续比较P[j]和P[k]。这是一个递归回溯的过程。如果回溯到k -1即next[0]说明没有任何相等前后缀那么next[j1] 0。C代码实现主流/李版定义void getNext(const string pattern, vectorint next) { int n pattern.size(); next.resize(n); next[0] -1; // 初始化 int j 0; // 指向前缀的末尾也代表next数组正在计算的位置的前一个位置 int k -1; // 指向当前匹配的前缀的末尾初始为-1 while (j n - 1) { // 计算 next[j1] if (k -1 || pattern[j] pattern[k]) { // 如果k回溯到起点或者当前字符匹配成功 j; k; // 这里可以进行优化形成nextval数组 // if (pattern[j] ! pattern[k]) next[j] k; // else next[j] next[k]; next[j] k; // 基础next数组赋值 } else { // 失配k回溯 k next[k]; } } }严版定义的代码调整 如果非要实现严版索引从1开始需要将字符串整体右移一位存储P[0]闲置或存长度代码逻辑完全一致只是初始化和赋值有1的偏移// 假设pattern[1..n]存储模式串next[1..n] void getNext_yan(const char pattern[], int next[], int n) { int j 1, k 0; next[1] 0; while (j n) { if (k 0 || pattern[j] pattern[k]) { j; k; next[j] k; } else { k next[k]; } } } // 注意严版教材中j和k的初始值、循环条件因代码表述可能略有不同但核心递归关系不变。4.2 基于不同next数组的KMP匹配过程next数组计算好后如何使用它进行匹配是关键。两种定义下的匹配代码有细微差别。主流/李版定义下的KMP匹配函数int kmpSearch(const string text, const string pattern) { vectorint next; getNext(pattern, next); // 获取的是主流版next数组 int i 0; // 主串指针 int j 0; // 模式串指针 int tLen text.size(), pLen pattern.size(); while (i tLen j pLen) { if (j -1 || text[i] pattern[j]) { // j -1 表示模式串第一个字符就失配特殊处理 i; j; } else { j next[j]; // 失配模式串指针回溯 } } if (j pLen) { return i - j; // 匹配成功返回起始位置 } return -1; // 未找到 }严版定义下的KMP匹配函数假设字符串从1开始存储int kmpSearch_yan(const char text[], const char pattern[], int tLen, int pLen) { int next[pLen 1]; // 多一位因为从1开始用 getNext_yan(pattern, next, pLen); int i 1, j 1; while (i tLen j pLen) { if (j 0 || text[i] pattern[j]) { // 注意这里是 j 0 i; j; } else { j next[j]; } } if (j pLen) { return i - pLen; } return 0; // 未找到 }核心差异对比失配特殊判断主流版判断j -1严版判断j 0。这是因为它们的next[0]或next[1]的哨兵值不同。指针回溯语句都是j next[j]但由于next数组值差1实际回溯的步幅是不同的。主流版回溯到的是前缀的末尾索引严版回溯到的是待比较字符的索引。初始化主流版i0, j0严版i1, j1。注意事项绝对不要混用如果你用严版教材的next数组值偏大却套用了网上主流从0开始的匹配代码一定会导致数组越界或逻辑错误。反之亦然。最稳妥的方法是理解并固定使用一种约定强烈推荐从0开始的主流约定然后所有的推导、计算、代码都基于此约定进行。5. 常见问题、调试技巧与终极选择建议在实际做题、考试或项目应用中关于KMP的next数组以下几个问题是最高频的。5.1 问题一手动计算next数组总是出错技巧遵循一个固定的“手算流程”写出模式串并标出索引建议从0开始。对于每个位置j写出其对应的前缀子串P[0...j-1]。列出该子串的所有真前缀和真后缀即不包括子串本身。找出最长的、相等的那个前缀和后缀记录其长度。这个长度就是主流定义下的next[j]。如果你需要严版的值将其1即可。示例快速计算对于“ababc”(索引0~4)j0:next[0] -1j1: 子串“a”长度0 -next[1]0j2: 子串“ab”长度0 -next[2]0j3: 子串“aba”前后缀“a”相等长度1 -next[3]1j4: 子串“abab”前后缀“ab”相等长度2 -next[4]25.2 问题二next数组和部分匹配表(Partial Match Table)是什么关系部分匹配表PMT是KMP算法原始论文中提出的概念。PMT[j]的值就是子串P[0...j]的最长相等前后缀的长度。注意这里包含了j位置的字符。对比我们的主流next数组定义next[j]是子串P[0...j-1]的最长相等前后缀长度。所以PMT[j-1]的值就等于next[j](对于j0)。next数组可以看作是PMT整体向右偏移一位并在头部插入一个-1。很多资料将PMT直接称为next数组这也是造成混淆的一个原因。我们只需要记住核心它们描述的都是“最长相等前后缀长度”这一信息只是存储的偏移量不同。5.3 问题三考试/刷题时应该用哪种国内考研/期末考试务必以你所用教材为准。如果指定教材是严蔚敏版那么答题包括手算next数组和编写算法步骤就必须按照其从1开始、next[j]为回溯位置的约定来。通常在题目中会明确字符串的存储起始位置。在线编程平台LeetCode, ACM等100%使用从0索引开始的主流定义。你几乎见不到需要从1开始存储字符串的题目。实现时就采用本文第4.1节给出的主流getNext函数和第4.2节的kmpSearch函数。实际工程项目同样使用主流定义。所有主流编程语言的字符串库都是0基索引。5.4 问题四如何调试KMP算法KMP算法不好理解写出来也容易有bug。我的调试方法是单元测试计算next函数单独测试getNext函数用几个经典的短模式串如“abab”,“aaaa”,“abcd”验证输出的next数组是否正确。可以对照手工计算的结果。打印中间状态在匹配循环中打印出每一步的i,j,text[i],pattern[j]以及是否匹配。这能帮你清晰地看到指针是如何移动和回溯的。使用可视化工具在网上搜索“KMP算法可视化”有很多动态演示网站。把自己算的next数组和程序跑的next数组输入进去看匹配过程能极大加深理解。边界条件测试测试空字符串、模式串比主串长、模式串只有一个字符、主串中不存在模式串等情况。5.5 终极建议与选择经过这么多年的学习和使用我的个人体会是彻底掌握从0索引开始的主流next数组定义。理由如下更符合编程直觉数组从0开始是编程世界的标准。更直接反映算法本质next[j]就是最长公共前后缀的长度概念清晰。通用性强在所有编程环境、算法竞赛、技术面试中都是唯一标准。易于记忆和推导手算时直接求长度即可无需额外1的转换。当你深刻理解了主流定义后再看严蔚敏老师的教材你就能明白那只是同一思想在不同“坐标系”索引从1开始下的表述。你可以轻松地在两种视角间进行转换而不是被“差1”这个问题所困扰。最后再分享一个记忆技巧把next数组想象成模式串的“故障回退地图”。当你在j位置“故障”失配时这张地图告诉你“别急前面已匹配的部分中从开头数next[j]个字符前缀和刚才最后next[j]个字符后缀是一样的所以我们可以直接把模式串滑到让这个前缀对齐刚才后缀的位置然后从P[next[j]]主流定义这个点继续往下比就行了。” 多想象这个过程多手算几个例子KMP和它的next数组就不再是黑盒了。