KMP 算法中next与nextval的计算详解本文统一采用0 下标模式串P的下标范围为0 ~ m-1并规定next[0] -1。不同教材可能采用 1 下标或 LPS/前缀函数因此数组数值可能不同但本质相同。计算数组时必须与对应的匹配代码保持同一种约定。1. 学习目标完成本文后你应该能够理解 KMP 算法为什么不需要回退主串指针准确说明next[j]的含义用手算和代码两种方式求出next数组理解nextval如何消除无效比较独立实现基于next或nextval的 KMP 字符串匹配。2. KMP 算法解决了什么问题设主串为S长度为n模式串为P长度为m当前已经成功匹配了P[0..j-1]下一次比较S[i]与P[j]时发生失配。朴素匹配会把主串起点向后移动一位再从模式串开头重新比较。KMP 利用已经匹配成功的模式串前缀直接计算模式串应回退到的位置主串 ... [已经匹配成功的部分] X ... 模式串 P[0 ........ j-1] P[j] ↑ 失配 KMP主串下标 i 不回退只令 j next[j]因此KMP 的关键不是“跳过字符”而是利用模式串自身的重复结构避免重新比较已经确定的信息。2.1 图解朴素匹配与 KMP 的根本区别第一次失配时普通匹配会移动主串起点而 KMP 保持i不变只令j next[j]。在图示案例中S[5]B、P[5]C失配后j跳到next[5]3随后直接比较S[5]B与P[3]B。核心结论“主串不回退”指的是i不向左移动j可以沿next链多次跳转。3. 前缀、后缀与最长相等前后缀3.1 前缀字符串的前缀是从第一个字符开始、但不包含整个字符串本身的子串。例如字符串ababa的真前缀为a ab aba abab3.2 后缀字符串的后缀是以最后一个字符结束、但不包含整个字符串本身的子串。ababa的真后缀为a ba aba baba3.3 最长相等前后缀最长 borderababa的前缀和后缀中最长的相等字符串是aba长度为3。这个长度就是 KMP 计算next的核心依据。4. 本文中next[j]的准确含义当模式串位置j发生失配时令j next[j]本文采用的定义是对于j 0next[j]等于子串P[0..j-1]的最长相等真前缀与真后缀的长度。形式化表示为next[0] -1 next[j] max{k | 0 k j且 P[0..k-1] P[j-k..j-1]}其中k 0表示不存在非空的相等前后缀next[0] -1是哨兵值用于统一匹配代码next[j]也是失配后模式串下一次参与比较的位置。为什么考察的是P[0..j-1]因为P[j]已经失配真正已经匹配成功的是它前面的j个字符P[0], P[1], ..., P[j-1]只有这部分信息可以被复用。5. 手工计算next的通用方法对模式串中的每个位置j取出位置j之前的子串P[0..j-1]写出它的所有真前缀和真后缀找到最长的相等前缀和后缀将其长度记为next[j]对j 0直接规定next[0] -1。图解示例P ABABAC对于j 5考察的是P[0..4] ABABA最长相等真前后缀是ABA长度为 3所以next[5] 3。字符P[5] C不参与next[5]的计算。示例模式串P ababaca字符和下标下标j0123456字符P[j]ababaca逐项计算j计算对象P[0..j-1]最长相等真前后缀长度next[j]0无无--11a空串002ab空串003abaa114ababab225ababaaba336ababac空串00最终结果下标 0 1 2 3 4 5 6 字符 a b a b a c a next -1 0 0 1 2 3 0补充案例P abcabca下标j0123456P[j]abcabcanext[j]-1000123nextval[j]-100-100-1例如j 6时失配前已匹配子串为abcabc最长相等真前后缀为abc所以next[6] 3。又因为P[6] P[3] a所以nextval[6] nextval[3] -1。6. 使用递推过程计算next手工枚举前后缀容易理解但代码不能对每个位置都重新枚举。KMP 使用两个指针递推i当前准备计算next[i1]的位置j当前候选的最长相等前后缀长度已知next[0..i]继续求后续值。核心规则若 j -1 或 P[i] P[j] i, j next[i] j 否则 j next[j]注意发生回退时只改变j不改变i。这正是 KMP 利用已有信息的体现。ababaca的关键递推过程步骤原i原j判断或操作新状态/结果10-1哨兵推进next[1] 0210b ! a回退j next[0] -131-1哨兵推进next[2] 0420a anext[3] 1531b bnext[4] 2642a anext[5] 3753c ! b回退j next[3] 1851c ! b回退j next[1] 0950c ! a回退j next[0] -1105-1哨兵推进next[6] 0C 语言实现voidbuild_next(constchar*p,intm,intnext[]){if(m0){return;}inti0;intj-1;next[0]-1;while(im-1){if(j-1||p[i]p[j]){i;j;next[i]j;}else{jnext[j];}}}Python 实现defbuild_next(pattern:str)-list[int]:ifnotpattern:return[]next_array[-1]*len(pattern)i,j0,-1whileilen(pattern)-1:ifj-1orpattern[i]pattern[j]:i1j1next_array[i]jelse:jnext_array[j]returnnext_array7. 为什么还需要nextvalnext数组已经能够保证 KMP 正确运行但某些情况下仍会产生必然失败的重复比较。假设在位置j失配并且P[j] P[next[j]]按照普通next下一步会令j next[j]但主串当前字符刚刚与P[j]比较失败而P[next[j]]又与P[j]相同因此下一次比较也一定失败。nextval的作用就是继续跳过这个无效位置。8.nextval的定义与计算公式先计算普通next再按以下规则优化nextval[0] -1 对于 j 0令 k next[j] 若 P[j] ! P[k] nextval[j] k 否则 nextval[j] nextval[k]换句话说若回退后比较的字符不同保留普通回退位置若回退后还是相同字符继续沿nextval向前跳。ababaca的nextval计算已知next [-1, 0, 0, 1, 2, 3, 0]逐项计算jP[j]k next[j]比较nextval[j]0a-1哨兵-11b0b ! a02a0a anextval[0] -13b1b bnextval[1] 04a2a anextval[2] -15c3c ! b36a0a anextval[0] -1最终结果下标 0 1 2 3 4 5 6 字符 a b a b a c a next -1 0 0 1 2 3 0 nextval -1 0 -1 0 -1 3 -1根据next生成nextval的 C 语言代码voidbuild_nextval(constchar*p,intm,constintnext[],intnextval[]){if(m0){return;}nextval[0]-1;for(intj1;jm;j){intknext[j];if(k0p[j]p[k]){nextval[j]nextval[k];}else{nextval[j]k;}}}Python 实现defbuild_nextval(pattern:str,next_array:list[int])-list[int]:ifnotpattern:return[]nextval[-1]*len(pattern)forjinrange(1,len(pattern)):knext_array[j]ifk0andpattern[j]pattern[k]:nextval[j]nextval[k]else:nextval[j]kreturnnextval9.nextval优化效果最明显的例子考虑模式串P aaaaab普通next下标 0 1 2 3 4 5 字符 a a a a a b next -1 0 1 2 3 4优化后的nextvalnextval -1 -1 -1 -1 -1 4当主串当前字符与某个a失配时普通next可能依次回退到多个仍然是a的位置产生重复失败nextval可以直接跳过这些位置。若某个a与主串当前字符失配普通next可能按4 → 3 → 2 → 1 → 0 → -1逐级回退这些位置仍然都是a。nextval可以直接跳到-1省去多次必然失败的比较。nextval只减少冗余比较不改变匹配结果。使用next和使用nextval都是正确的 KMP。9.1 案例一包含多次回退的匹配过程主串S ABABABCABABABCAB模式串P ABABAC。这个主串最终不包含模式串但非常适合观察j沿next链多次回退而i始终不向左移动。步骤ij比较或操作结果155S[5]B与P[5]C失配jnext[5]3253S[5]B与P[3]B匹配i6,j4364S[6]C与P[4]A失配j2462S[6]C与P[2]A失配j0560S[6]C与P[0]A失配j-166-1触发哨兵规则i7,j0770S[7]A与P[0]A匹配继续扫描每次跳转都对应一个仍可能成为匹配开头的前后缀。被跳过的位置已经由模式串结构证明不可能成功因此不会漏掉匹配。9.2 案例二最终匹配成功设S ABABABCABABACABP ABABAC。扫描到主串下标 7 后出现完整匹配主串下标789101112S[i]ABABAC模式下标012345P[j]ABABAC匹配结束时i13、j6m所以匹配起点为i-j7。应用案例编辑器查找、日志关键词扫描、DNA/蛋白质序列片段定位、网络数据流中的固定模式检测。10. 完整 KMP 匹配代码10.1 使用任意回退表进行匹配intkmp_search(constchar*text,intn,constchar*pattern,intm,constinttable[]){if(m0){return0;}inti0;intj0;while(injm){if(j-1||text[i]pattern[j]){i;j;}else{jtable[j];}}return(jm)?(i-j):-1;}调用时intnext[m];intnextval[m];build_next(pattern,m,next);build_nextval(pattern,m,next,nextval);intpos1kmp_search(text,n,pattern,m,next);intpos2kmp_search(text,n,pattern,m,nextval);pos1与pos2的结果应完全相同只是比较次数可能不同。10.2 完整可运行示例#includestdio.h#includestring.hvoidbuild_next(constchar*p,intm,intnext[]){if(m0)return;inti0;intj-1;next[0]-1;while(im-1){if(j-1||p[i]p[j]){i;j;next[i]j;}else{jnext[j];}}}voidbuild_nextval(constchar*p,intm,constintnext[],intnextval[]){if(m0)return;nextval[0]-1;for(intj1;jm;j){intknext[j];if(k0p[j]p[k]){nextval[j]nextval[k];}else{nextval[j]k;}}}intkmp_search(constchar*text,intn,constchar*pattern,intm,constinttable[]){if(m0)return0;inti0;intj0;while(injm){if(j-1||text[i]pattern[j]){i;j;}else{jtable[j];}}return(jm)?(i-j):-1;}intmain(void){constchar*textbacbababadababacambabacaddababacasdsd;constchar*patternababaca;intn(int)strlen(text);intm(int)strlen(pattern);intnext[64];intnextval[64];build_next(pattern,m,next);build_nextval(pattern,m,next,nextval);printf(next: );for(inti0;im;i)printf(%d ,next[i]);printf(\\nnextval: );for(inti0;im;i)printf(%d ,nextval[i]);intposkmp_search(text,n,pattern,m,nextval);printf(\\nmatch position: %d\\n,pos);return0;}预期输出next: -1 0 0 1 2 3 0 nextval: -1 0 -1 0 -1 3 -1 match position: 1011. 时间复杂度与空间复杂度11.1 构造数组构造nextO(m)构造nextvalO(m)额外数组空间O(m)。11.2 字符串匹配KMP 匹配过程中主串指针i不回退模式串指针j虽然可能多次回退但总操作次数仍为线性级别。因此匹配时间复杂度为O(n m)其中O(m)用于预处理模式串O(n)用于扫描主串。12. 与其他教材记法的对应关系12.1 1 下标版本有些教材令模式串下标为1..m并规定next[1] 0与本文 0 下标版本的对应关系通常为next_1based[j 1] next_0based[j] 1例如ababaca本文 0 下标-1 0 0 1 2 3 0 常见 1 下标 0 1 1 2 3 4 112.2 LPS 或前缀函数pi很多算法题使用 LPSLongest Prefix Suffix或前缀函数pipi[k] P[0..k] 的最长相等真前后缀长度本文next与pi的关系为对于 j 1next[j] pi[j - 1]因此看到不同数组时先检查下标从 0 还是 1 开始首元素是-1、0还是1数组表示“失配后的比较位置”还是“当前前缀的最长 border 长度”匹配代码是否与数组定义配套。13. 常见错误错误 1把P[j]也纳入next[j]的计算next[j]考察的是已经匹配成功的部分P[0..j-1]不是P[0..j]。错误 2把最长公共子串当成最长前后缀候选字符串必须同时满足从原串第一个字符开始在原串最后一个字符结束。出现在中间的相同子串不能使用。错误 3真前缀或真后缀包含整个字符串“真”前缀和“真”后缀不能等于字符串本身否则每个字符串都会与自身完全相等失去意义。错误 4混用不同版本的next例如使用next[0] -1的数组却配套使用next[0] 0的匹配代码可能导致死循环、越界或错误结果。错误 5构造next时失配后同时移动i失配时只应执行j next[j]不能移动i因为当前P[i]还需要与更短候选前缀继续比较。错误 6认为nextval会改变匹配结果nextval只是进一步跳过必然失败的位置匹配结果与普通next完全一致。14. 练习题练习 1计算模式串abcabca的next与nextval。练习 2计算模式串aaaaab的next与nextval并说明为什么nextval的优化明显。练习 3模式串ababaca在位置j 5失配时普通next令j回退到哪里为什么不能直接回退到j 2参考答案练习 1 P a b c a b c a next -1 0 0 0 1 2 3 nextval -1 0 0 -1 0 0 -1 练习 2 P a a a a a b next -1 0 1 2 3 4 nextval -1 -1 -1 -1 -1 4 练习 3 next[5] 3因此先回退到 j 3。 P[0..4] ababa 的最长相等真前后缀为 aba长度是 3 长度为 2 的前缀 ab 并不是 ababa 的后缀因此不能直接取 2。15. 速记总结1. next[j] 看的是 P[0..j-1]。 2. next[j] 等于这段子串的最长相等真前后缀长度。 3. 本文约定 next[0] -1。 4. 失配时主串指针不回退只执行 j next[j]。 5. 若 P[j] P[next[j]]普通回退会再次必然失配。 6. nextval 用 nextval[next[j]] 跳过这种无效比较。 7. next 与 nextval 都正确nextval 通常比较次数更少。 8. 不同教材数组不同首先核对下标和哨兵约定。