★ FEATURED ARTICLE 1. 从朴素匹配的痛点说起为什么非要搞一个next数组我第一次接触KMP算法的时候和大多数人一样先看了一堆数学公式什么前缀函数、失配函数、状态转移看完直接劝退。后来自己动手画图推导才真正明白next数组到底是什么东西。这里我不打算用任何数学符号就用走路、划线和“悔棋”的思路把整个KMP算法next数组讲透。先说朴素字符串匹配的思路。假设你手里有一个文本串就是一长串字符要在里面找一个模式串就是你想找的那段字符。朴素的做法很直接从文本串的每一个位置开始依次和模式串的字符比对一旦发现对不上就把模式串整体往右挪一位然后重新从头比对。举个例子。文本串是ABACABADABACABA模式串是ABAD。朴素匹配的过程大概是这样的文本串: A B A C A B A D A B A C A B A 模式串: A B A D 比对: A对A, B对B, A对A, C对D——对不上这时候朴素匹配的做法是什么把模式串往右挪一位重新从模式串的第一个字符开始比对文本串: A B A C A B A D A B A C A B A 模式串: A B A D 比对: A对B——第一个字符就对不上然后就继续挪、继续比。这样做的效率问题非常明显文本串里已经比对过的字符随着模式串的移动会被反复比较。最极端的情况下比如文本串全是AAAAAAAAAAAAB模式串是AAAAAB每一次都要比到最后一个字符才发现不对然后挪一位再从开头比时间复杂度直接到了O(n*m)文本串一长就扛不住。KMP算法的核心思路是模式串自己先做一次“预分析”把每个位置上匹配失败之后应该跳到哪里的信息提前算好存在一个数组里这个数组就是next数组。匹配的时候文本串的下标永远不回溯只是模式串的位置根据next数组跳来跳去时间复杂度是O(nm)。说句实在话KMP算法本身的匹配过程学起来很快真正劝退99%的人的是next数组的求解。因为网上很多教程一上来就是next[i] k, 满足 s[0..k-1] s[i-k..i-1]我看着这玩意儿的时候心里只有一句话这是在说什么所以这篇文章我换一种方式完全不碰数学符号只用图形来推next数组。你看完之后会发现next数组就是模式串自己的“前后缀匹配长度表”而求解这个表的过程本质上就是一个“自己在自己身上跑匹配”的过程。2. next数组到底是什么前后缀的匹配关系2.1 从一个生活场景理解前缀后缀要理解next数组先得理解什么是字符串的“前缀”和“后缀”。这两个名词听起来很高深其实就是字面意思。假设有一个字符串ABA它的前缀就是从前面截取的一些子串A、AB注意完整的ABA本身不算它的后缀就是从后面截取的一些子串A、BA同样完整的ABA本身不算再举个例子字符串ABCAB前缀有A、AB、ABC、ABCA后缀有B、AB、CAB、BCAB现在注意看ABCAB里前缀AB和后缀AB是相同的。也就是说这个字符串的开头两个字符和结尾两个字符是一样的。这种“既是开头一部分又是结尾一部分”的子串就叫公共前后缀。AB就是ABCAB的一个公共前后缀它的长度是2。判断公共前后缀是为了什么我打一个比方。你在一个迷宫里走路走过的路标成了一条线。你走到某个位置发现走错了需要退回去你最希望的是退到一个“能接上之前线索”的位置而不是退回到起点全部重走。字符串匹配也一样模式串在某个位置失配了如果能找到“已经比对成功的部分”里最长的那个公共前后缀就可以把模式串跳到那个后缀和前缀重合的位置已经比对成功的部分就不用再比了。2.2 next数组的每一格到底存什么next数组和模式串等长它的下标从0开始。next[i]的意思是模式串的前i个字符组成的子串通俗说就是截止到当前字符为止的这一段中最长公共前后缀的长度。注意这里说的“前i个字符”是包含当前字符在内的。等一下这里有一个关键细节。不同教程对next数组的定义有两种流派一种存的是“最长公共前后缀的长度”另一种存的是“失配后应该跳到的下标位置”。这两种在数值上差1很多新手在这里被搞晕。我的建议是先用“最长公共前后缀的长度”来理解代码实现的时候再根据自己习惯调整。为了统一这篇文章里我把next[i]定义为模式串从下标0到下标i这一段子串中最长公共前后缀的长度。举个例子模式串是ABABCi0子串是A它没有真前缀也没有真后缀因为整个字符串本身不算所以公共前后缀长度为0next[0]0i1子串是AB前缀A后缀B不相同所以next[1]0i2子串是ABA前缀有A、AB后缀有A、BA公共的是A长度1所以next[2]1i3子串是ABAB前缀有A、AB、ABA后缀有B、AB、BAB公共的是AB长度2所以next[3]2i4子串是ABABC公共前后缀是A吗前缀有A、AB、ABA、ABAB后缀有C、BC、ABC、BABC没有公共的所以next[4]0看明白了吗每一格的数就是看“已经过的这串字符”里开头和结尾能对上多少。就这么简单。2.3 为什么这个长度有用图解失配跳转假设文本串是ABABABC模式串是ABABC。它们的next数组刚才已经算出来了一部分完整的next数组是[0, 0, 1, 2, 0]。现在开始匹配文本串: A B A B A B C 模式串: A B A B C 比对: A对A, B对B, A对A, B对B, C对C?——不对文本串第5个是B具体的比对过程是这样的0 1 2 3 4 5 6 文本: A B A B A B C 模式: A B A B C ^ 失配位置在模式串下标4此时模式串已经成功匹配了下标0到3这四个字符也就是ABAB。失配发生在模式串下标4字符C的位置上。朴素匹配会怎么做把模式串整体往右挪一位重新从模式串的开头比。但KMP不这么做。KMP的思路是已经匹配过的部分ABAB中后缀AB和前缀AB是公共前后缀长度为2。这说明什么说明文本串里“刚才匹配过的部分”的末尾两个字符是AB而这正好和模式串开头两个字符AB一致。所以我可以直接把模式串往右跳让模式串下标0和1与文本串里这堆已匹配字符的末尾两个位置对齐然后从模式串下标2继续比对。画出来就是这样第一轮: 文本: A B A B A B C 模式: A B A B C 失配于模式串下标4 第二轮: 文本: A B A B A B C 模式: A B A B C ↑ 模式串跳到了下标2继续比对 ↑ 文本串下标4和模式串下标2都是A继续往后注意文本串的下标有没有回退没有。第一轮比对到文本串下标4的时候失配第二轮直接从文本串下标4继续只是模式串的下标从4变成了2。这就是KMP高效的核心——文本串一路向前绝不回头。那为什么是跳到2而不是跳到1或者3因为ABAB的最长公共前后缀长度是2跳到2能保证“已经确认相同”的部分前缀AB不被重复比对同时又不会遗漏中间可能存在的匹配起点。如果你跳过头了把模式串挪太多可能会错过正确匹配如果你跳少了已经验证过的字符还要再比一遍效率就低了。最长公共前后缀就是那个“不多不少”的跳转距离。3. 完全图解next数组的推导过程爱怎么走就怎么走3.1 手推一个完整的例子ABABAC网上讲next数组推导一上来就甩代码很多人背下来了但完全不知道循环里每个分支在干什么。这一小节我们只看图形和“指针走路”的过程先不碰任何代码。模式串设为ABABAC长度为6。我们要求next[0]到next[5]。第一步令i从1开始往右走j从0开始。模式串: A B A B A C 下标: 0 1 2 3 4 5当前i1窗口是AB。我们看这串字符里前缀和后缀是否相同字符串: A B 前缀: A 后缀: B 不匹配公共前后缀长度是0所以next[1]0。第二步i移动到2窗口是ABAj现在还在0。我们看这窗口的开头和结尾字符串: A B A 前缀: A 后缀: A 匹配上了长度1变为1公共前后缀长度是1所以next[2]1。现在有一个很重要的操作因为这个窗口的公共前后缀长度为1所以我们要让j跟着跳到1的位置。为什么因为j本来是指向模式串开头的既然前缀和后缀匹配上了说明模式串的第0个字符和当前窗口的最后一个字符是相同的下一次比较我们应该用模式串的下一个字符下标1去跟新窗口的末尾比较。到这里我可以先插一句这个“j跟随窗口末尾移动”的思想是整个next数组求解的关键。你暂时不用管j的值是干嘛的只需要知道j表示“当前已经匹配上的公共前后缀的长度”。第三步i移动到3窗口是ABAB。此时j1意思是前面已经确认前缀长度为1也就是模式串下标0的A和窗口末尾之前的某个A对上了。那么我们要看的是模式串第j个字符也就是下标1的B能不能跟窗口末尾的字符当前i位置的字符对上。当前窗口末尾的字符是B。模式串: A B A B A C 下标: 0 1 2 3 4 5 窗口: A B A B 要比较: 模式串下标1的B 与 窗口末尾的B 比对成功j从1变成2公共前后缀长度是2所以next[3]2。为什么这么比较一次就能确定长度是2因为上一步我们已经确认了AB的前后缀关系现在窗口末尾新增了一个B模式串前缀中刚好下一个字符也是B两者相等就说明当前窗口的最长公共前后缀长度在原来的基础上又延长了一位。这是一种递推的思想不重新从头比较而是在以前结果的基础上延伸。第四步i移动到4窗口是ABABAj2。我们要比较模式串下标2的A和窗口末尾的字符A。模式串: A B A B A C 下标: 0 1 2 3 4 5 窗口: A B A B A 要比较: 模式串下标2的A 与 窗口末尾的A 比对成功j从2变成3next[4]3。第五步i移动到5窗口是ABABACj3。我们要比较模式串下标3的B和窗口末尾的字符C。模式串: A B A B A C 下标: 0 1 2 3 4 5 窗口: A B A B A C 要比较: 模式串下标3的B 与 窗口末尾的C 比对失败此时j3但比对失败了该怎么办这是最让人头疼的地方很多教程在这里就直接甩一个while循环把jnext[j-1]甩出来。我完全图解一下这到底是怎么回事。当前窗口是ABABAC我们之前一直假设公共前后缀长度是3即ABA但现在末尾的C和模式串第3个字符B对不上。说明“长度为3”这个假设不成立。那我们要退回去看更短一点的公共前后缀是否存在。怎么退注意我们之前确认过窗口末尾的ABA和窗口开头的ABA是对上的。想象一下在窗口开头这一侧有一个模式串的局部ABABA在窗口末尾这一侧又有一个局部ABABA。虽然长度为3的延伸失败了但在这两个局部里ABA这个整体是有内部结构的。既然ABA自身的前缀A和后缀A相同那么窗口末尾侧的ABA的最后一位A其实也和窗口开头侧的ABA的第一位A对应上了。这个绕口直接看图窗口: A B A B A C 前侧局部: A B A 后侧局部: A B A后侧局部的A B A它的后缀A和前侧局部的ABA的前缀A是不是同一个概念是。所以我们可以把j回退到“长度为2时的公共前后缀长度”也就是next[2]的值j变成1。然后重新比较模式串下标1的B和窗口末尾的C还是对不上。于是再回退j变成next[1]的值也就是0再比较模式串下标0的A和窗口末尾的C还是对不上。到这里说明整个窗口ABABAC确实没有公共前后缀next[5]0。完整推完模式串ABABAC的next数组是[0, 0, 1, 2, 3, 0]。3.2 图解“失败后的回退”为什么是jnext[j-1]上面第五步的操作是整个next数组求解里最核心、最容易出错的地方。我再把这个回退过程单独拿出来讲得更细一点。还是用模式串ABABAC推next[5]时的窗口是ABABACj3比对B和C失败。失败后为什么不是直接让j0重新来因为窗口的末尾部分可能还有一些和开头部分相同的片段直接归零会把线索全丢掉。举个例子窗口是ABABAB它的最长公共前后缀是4ABAB。假设在推next的时候j4尝试往后延伸时失败此时回退到jnext[3]2仍然是AB如果后面的字符能接上还能找到长度为2、4甚至更长的公共前后缀。如果直接归零就可能错过隐藏的匹配。用图形来看ABABAC这个窗口中前3个字符ABA和后3个字符ABA是相同的。我们要找的公共前后缀只能在两个ABA内部找。下一个候选长度就是ABA自己的最长公共前后缀长度。ABA的最长公共前后缀是1A所以j从3回退到1。一句话解释当长度为j的公共前后缀无法延伸时新的候选长度就是“前缀部分自身的最长公共前后缀长度”因为公共前后缀一定是前缀的前缀和后缀的后缀同时相等的东西。这里我不展开任何“数学证明”你只要记住这个操作模式比对失败后j回退到next[j-1]直到j等于0或者比对成功。回到0说明整个窗口没有公共前后缀。3.3 再推一个更容易出错的反例AAABAAA模式串AAABAAA看起来很规整但推的时候很容易犯迷糊。按照上面说的规则我们一步步来。窗口A没有前缀后缀next[0]0。i1窗口AAj0比较模式串下标0的A和窗口末尾的A相等j1next[1]1。i2窗口AAAj1比较模式串下标1的A和窗口末尾的A相等j2next[2]2。i3窗口AAABj2比较模式串下标2的A和窗口末尾的B失败。j回退到next[1]1比较模式串下标1的A和窗口末尾的B失败。j回退到next[0]0比较模式串下标0的A和窗口末尾的B失败。next[3]0。i4窗口AAABAj0比较模式串下标0的A和窗口末尾的A相等j1next[4]1。i5窗口AAABAAj1比较模式串下标1的A和窗口末尾的A相等j2next[5]2。i6窗口AAABAAAj2比较模式串下标2的A和窗口末尾的A相等j3next[6]3。最终next数组是[0, 1, 2, 0, 1, 2, 3]。注意看AAABAAA中从下标0到6整体看最长公共前后缀是3AAA对AAA这没错。但是这个数组不是单调递增的——中间B的出现让next在i3的地方直接掉到0。这说明next数组不一定是递增的也不一定每次只能加1或者回退1它的变化是由字符本身决定的不要试图找单调规律。4. 动手实现next数组求解代码逐行解读4.1 手写next数组的代码与注释理解了上面的图解过程代码其实就是把“j走一步、比对、失败回退”这几件事翻译成编程语言。我用C风格写出最经典的求解函数然后逐行讲。void getNext(char* p, int* next) { int len strlen(p); next[0] 0; // 单个字符没有公共前后缀 int j 0; // j代表当前已匹配的公共前后缀长度 for (int i 1; i len; i) { // i从1开始因为next[0]已经确定 // 如果当前字符对不上就回退j while (j 0 p[i] ! p[j]) { j next[j - 1]; // 关键回退操作 } // 如果对上了j加1 if (p[i] p[j]) { j; } next[i] j; // 记录当前窗口的最长公共前后缀长度 } }逐行对应到前面图解的步骤每次循环的i就是图里的“窗口末尾”位置。j就是“已经确认的公共前后缀长度”它同时是指向模式串前缀下一个待比较字符的下标。循环开始后先处理“对不上怎么办”。while循环反复回退j直到j变成0或者p[i]等于p[j]。回退之后再判断一次p[i]和p[j]是否相等如果相等j加1。最后把j记录下来就是next[i]。很多人问为什么while循环里一直没有比较p[i]和p[j]因为while的退出条件就是“j变成0或者p[i]p[j]”退出之后再走if判断本质上是一样的。有一点要注意这里p[j]是模式串中下标为j的字符而从循环开始到现在j始终小于等于i因为每次j最多增加1。所以p[j]访问不会越界。j初始为0i初始为1这个错位保证了“窗口”至少有两个字符。4.2 用刚才的AAABAAA验证代码逻辑把AAABAAA代入代码脑内走一遍i1j0p[1]Ap[0]A相等j1next[1]1。i2j1p[2]Ap[1]A相等j2next[2]2。i3j2p[3]Bp[2]A不等进入whilejnext[1]1p[3]Bp[1]A不等再回退jnext[0]0循环结束。p[3]Bp[0]A不等j不变next[3]0。i4j0p[4]Ap[0]A相等j1next[4]1。后续几步代码执行结果和手推一致。这里我想强调一个容易让你产生困惑的点在i3的循环里j先回退到1然后回退到0中间没有直接再次尝试j1的状态。为什么因为j1代表的公共前后缀长度是1也就是窗口AAA里的前缀A和后缀A相同而当前窗口AAAB想要延伸这个长度到2需要模式串下标1的字符B和窗口末尾的B对上但并没有对上。所以回退到1之后要立刻尝试新的延伸发现不行继续回退。这个逻辑在代码里就是while循环一直回退直到找到能让p[j]等于p[i]的j为止。4.3 匹配阶段的代码next数组怎么用next数组算好之后匹配阶段的代码反而简单很多。int kmpSearch(char* s, char* p, int* next) { int n strlen(s), m strlen(p); int j 0; // 模式串当前匹配到的位置 for (int i 0; i n; i) { // 文本串下标只往前走 // 失配时模式串位置回退 while (j 0 s[i] ! p[j]) { j next[j - 1]; } if (s[i] p[j]) { j; } // 匹配完成 if (j m) { return i - m 1; // 返回完全匹配的起始下标 } } return -1; }这段代码和getNext的结构很像都是“能往前走就走不能走就回退”。区别在于getNext里的p是对模式串自己比较匹配阶段里的s是文本串和模式串比较。有一个细节需要说明当j等于0的时候说明模式串一个字符都没匹配上此时失配的话模式串位置没法回退只能让文本串的i继续往后走。while (j 0 ...)这个条件就处理了这种情况j为0时不会进入循环。4.4 两种next数组定义的差异避坑前面说next数组有两种定义流派这里展开讲清楚不然你查资料的时候一定会被搞懵。第一种流派next[i]存最长公共前后缀长度。就像本文一直用的这种。匹配阶段失配时模式串回退到next[j-1]。第二种流派next[i]存失配后应该跳到的下标位置。比如有人的next数组定义为“当第i个字符失配时下一次从模式串的哪个下标开始比较”那next[i]可能等于第一种定义里next[i-1]的值或做进一步优化。两种定义在代码里差异巨大。如果你看到别人的代码里初始化和回退方式跟本文不一样先判断对方采用的是哪种定义再去看代码逻辑。这里给一个通用的核实办法用一个简单的模式串比如ABABC手工推出对方的next数组再跑一遍匹配看结果是否一致。只要逻辑自洽哪种定义都能正确工作。4.5 优化版next数组为什么有时候next的值要减一很多进阶教材还会提到一个“优化版next数组”——失配后让j跳得更远。看一个经典例子。模式串AAAAAB朴素计算的next数组是[0, 1, 2, 3, 4, 0]。如果匹配时遇到模式串下标3失配j回退到next[2]2然后比较p[2]和当前文本字符。但如果当前文本字符和p[3]失配而p[3]等于p[2]都等于A那p[2]和当前文本字符也必然失配。于是j白跳了还要再跳一次。优化版的思路是回退时如果发现p[j]和p[new_j]相同就继续回退跳过一个必然失配的位置。这一优化通常被称为nextval数组。具体实现是void getNextval(char* p, int* nextval) { int len strlen(p); nextval[0] 0; int j 0; for (int i 1; i len; i) { while (j 0 p[i] ! p[j]) { j nextval[j - 1]; } if (p[i] p[j]) { j; } // 优化如果下一个位置的字符相同继续回退 if (p[i 1] p[j]) { nextval[i] nextval[j - 1]; } else { nextval[i] j; } } }对初学者我的建议是先彻彻底底搞懂普通next数组再去看nextval。因为nextval的代码是在next数组基础上加了一个“跳过相同字符”的判断如果你连next数组的推导都不熟这个优化会让你更晕。5. 常见问题与排查技巧实录5.1 为什么我的next数组第一个值有时候是-1查资料的时候你十有八九会看到有人写next[0]-1。这不是错误而是另一种定义流派。-1的含义是“失配后模式串完全回到起点之前”配合代码里j -1的判定可以让匹配逻辑更统一——无论什么情况失配i都加1j也加1。这种定义和本文的next[0]0在本质上是等价的只是偏移量不同。如果你在代码调试时发现别人贴出的next数组全是减一的值先不要怀疑自己算错了看一下对方是不是用了-1流派。5.2 递归回退会不会死循环在getNext的while循环里j next[j - 1]表面上看j在不断变小会不会跳回0之后还在跳不会。因为next[j-1]始终小于jnext数组存的是公共前后缀长度长度必然小于子串本身长度所以j严格递减最终到达0while循环的j 0条件会退出。在实际调试中唯一可能导致死循环的情况是你把next数组本身写错了比如next[j-1]的值等于j。所以如果代码卡死先输出next数组检查数值是否满足“next[i] i”这个基本性质。5.3 边界条件模式串长度为1模式串长度为1时getNext里循环压根不会执行i从1开始len-10next数组只有一个元素next[0]0。匹配阶段j0文本串每个字符都和p[0]比较一旦相等就匹配成功。这个场景看起来简单但很多人在写getNext时忘记处理“模式串为空”的情况直接strlen(空串)导致下标越界。写代码前先判空是很好的习惯。5.4 中文字符串的next数组怎么算如果你用C语言的char数组处理UTF-8编码的中文每个中文字符占3个字节按字节算next数组会把一个汉字拆成三个字节结果完全不对。处理中文字符串时建议转成宽字符wchar_t或者直接用支持按字符索引的语言比如Python的字符串、Java的String、Go的rune数组。这个坑我踩过第一次拿KMP匹配中文文本时匹配位置总是偏的查了半天才发现是字节序的问题。5.5 调试next数组的实用技巧手推next数组很容易出错我给两个自查方法。方法一用暴力法验证。写一个暴力求解next数组的函数不做任何优化直接把每个窗口的所有前缀后缀都列出来比较然后用它和你手推/优化的代码结果比对。暴力法虽然慢但逻辑极其简单非常适合验证。void bruteNext(char* p, int* next) { int len strlen(p); for (int i 0; i len; i) { // 考虑子串 p[0..i] int maxLen 0; for (int k 1; k i; k) { // k是公共前后缀的候选长度 int ok 1; for (int x 0; x k; x) { if (p[x] ! p[i - k 1 x]) { ok 0; break; } } if (ok) maxLen k; } next[i] maxLen; } }方法二用匹配结果反推。找一个文本串用暴力的朴素匹配找出所有匹配位置再用KMP匹配看看结果是否一致。如果KMP结果和朴素匹配结果一致说明你的next数组大概率是对的如果不一致用手推一步步核对。5.6 一个常被忽略的性能细节预处理开销KMP的优势在于O(nm)的复杂度但如果模式串很短预处理next数组的开销就不容忽视。模式串长度为1时预处理虽然只有常数时间但调用的开销和一次朴素匹配几乎一样。实际工程中如果文本串很短朴素匹配反而更快。我在做日志文本匹配时文本行长度普遍不超过200字符模式串也经常是简单的关键字这种情况下用标准库的strstr或者正则表达式就够了没必要自己实现KMP。KMP适合的场景是文本串超长、模式串较长、有大量重复搜索需求。6. 扩展思考next数组思想在别的地方的应用KMP的next数组思想本质上是“对自身结构的预分析”。这种思想在计算机领域不止出现在字符串匹配中理解next数组之后你可以类比理解很多东西。在字符串压缩里LZ77系列算法用“滑动窗口前向缓冲”的做法本质是找文本中重复出现的片段。你找重复片段时用到的“最长匹配”思路和找最长公共前后缀一脉相承。在构建单词查找树也就是Trie的时候如果要在多个字符串之间共享前缀AC自动机会在每个节点上维护一个失败指针这个失败指针的含义跟next数组几乎一样都是“失配后跳到哪个位置继续匹配”。AC自动机的fail指针构建就是KMP的next数组从单模式串扩展到多模式串的版本。我自己的体会是KMP的next数组是很多高级算法的地基。理解了它后面接触AC自动机、后缀数组、回文自动机的时候很多概念都是熟悉的不会那么吃力。还有一个小场景判断一个字符串是不是由某个子串重复拼接而成。比如ABABABAB是不是ABAB重复出来的这可以直接用next数组的最后一个值来判断。如果字符串长度为n最后一个位置的next值是n - 周期串长度那么用n减去这个值如果能整除n说明存在循环节。这个技巧在面试题里经常出现算是next数组的一个冷门又实用的应用。7. 个人实操中的一些体会KMP算法是我学的时候觉得最难、回头看又觉得最巧妙的一个算法。难点不在于代码本身而在于next数组的语义太抽象很多教程又习惯性地堆公式。我强烈建议你自己拿一张纸手动推两三个模式串的next数组比如ABABAC、AAABAAA、ABCDABD。推的时候不要照着代码抄就用“画窗口、比开头结尾、失败就回退到上一个前缀的公共前后缀长度”这个思路走。一个更笨但极其有效的方法是把模式串的每个前缀都写出来逐个标出它的最长公共前后缀长度。比如模式串ABCDABD把前缀列出来A- 0AB- 0ABC- 0ABCD- 0ABCDA- 1AABCDAB- 2ABABCDABD- 0然后把这些数字填进next数组就是[0, 0, 0, 0, 1, 2, 0]。这个方法虽然慢但对于建立直觉非常有帮助。等你推了三五个字符串之后再回来看代码会发现代码里的每一个分支你都清清楚楚知道它在干什么根本不需要背。还有一点匹配阶段的KMP和预处理的KMP非常相似很多刚学的人会搞混。我的记忆方法是预处理是“模式串自己和自己比”匹配是“文本串和模式串比”但两者的回退逻辑完全一样——失配后看已匹配部分的最长公共前后缀长度跳到对应位置继续比。把这两个概念分开代码就不会写串。如果你准备面试KMP几乎是必考题之一但面试官更看重的是你能不能把next数组的推导过程讲明白。这也是我写这篇完全图解文章的原因不背公式不背代码用图形把逻辑走一遍比背十遍代码都管用。最后再分享一个小技巧调试KMP时在关键位置加打印把当前i、j、next[j-1]的值都打印出来对照手推过程一步步核对比盯着代码发呆高效得多。我当年就是靠这个方法花了几个小时把所有疑惑全部理清的。
阅读完成 · 觉得有帮助？
