KMP算法_next与nextval计算详解_图解案例版

KMP 算法中next与nextval的计算详解

本文统一采用0 下标：模式串P的下标范围为0 ~ m-1，并规定next[0] = -1。不同教材可能采用 1 下标或 LPS/前缀函数，因此数组数值可能不同，但本质相同。计算数组时，必须与对应的匹配代码保持同一种约定。

1. 学习目标

完成本文后，你应该能够：

1. 理解 KMP 算法为什么不需要回退主串指针；
2. 准确说明next[j]的含义；
3. 用手算和代码两种方式求出next数组；
4. 理解nextval如何消除无效比较；
5. 独立实现基于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 abab

3.2 后缀

字符串的后缀是以最后一个字符结束、但不包含整个字符串本身的子串。

ababa的真后缀为：

a ba aba baba

3.3 最长相等前后缀（最长 border）

ababa的前缀和后缀中，最长的相等字符串是aba，长度为3。

这个长度就是 KMP 计算next的核心依据。

4. 本文中next[j]的准确含义

当模式串位置j发生失配时，令：

j = next[j]

本文采用的定义是：

对于j > 0，next[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：

1. 取出位置j之前的子串P[0..j-1]；
2. 写出它的所有真前缀和真后缀；
3. 找到最长的相等前缀和后缀；
4. 将其长度记为next[j]；
5. 对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

字符和下标：

逐项计算

最终结果：

下标： 0 1 2 3 4 5 6 字符： a b a b a c a next： -1 0 0 1 2 3 0

补充案例：P = abcabca

例如j = 6时，失配前已匹配子串为abcabc，最长相等真前后缀为abc，所以next[6] = 3。又因为P[6] = P[3] = a，所以nextval[6] = nextval[3] = -1。

6. 使用递推过程计算next

手工枚举前后缀容易理解，但代码不能对每个位置都重新枚举。KMP 使用两个指针递推：

• i：当前准备计算next[i+1]的位置；
• j：当前候选的最长相等前后缀长度；
• 已知next[0..i]，继续求后续值。

核心规则：

若 j == -1 或 P[i] == P[j]： i++, j++ next[i] = j 否则： j = next[j]

注意：发生回退时，只改变j，不改变i。这正是 KMP 利用已有信息的体现。

ababaca的关键递推过程

C 语言实现

voidbuild_next(constchar*p,intm,intnext[]){if(m<=0){return;}inti=0;intj=-1;next[0]=-1;while(i<m-1){if(j==-1||p[i]==p[j]){++i;++j;next[i]=j;}else{j=next[j];}}}

Python 实现

defbuild_next(pattern:str)->list[int]:ifnotpattern:return[]next_array=[-1]*len(pattern)i,j=0,-1whilei<len(pattern)-1:ifj==-1orpattern[i]==pattern[j]:i+=1j+=1next_array[i]=jelse:j=next_array[j]returnnext_array

7. 为什么还需要nextval

next数组已经能够保证 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]

逐项计算：

最终结果：

下标： 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(m<=0){return;}nextval[0]=-1;for(intj=1;j<m;++j){intk=next[j];if(k>=0&&p[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)):k=next_array[j]ifk>=0andpattern[j]==pattern[k]:nextval[j]=nextval[k]else:nextval[j]=kreturnnextval

9.nextval优化效果最明显的例子

考虑模式串：

P = aaaaab

普通next：

下标： 0 1 2 3 4 5 字符： a a a a a b next： -1 0 1 2 3 4

优化后的nextval：

nextval： -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始终不向左移动。

每次跳转都对应一个仍可能成为匹配开头的前后缀。被跳过的位置已经由模式串结构证明不可能成功，因此不会漏掉匹配。

9.2 案例二：最终匹配成功

设S = ABABABCABABACAB，P = ABABAC。扫描到主串下标 7 后，出现完整匹配：

匹配结束时i=13、j=6=m，所以匹配起点为i-j=7。

应用案例：编辑器查找、日志关键词扫描、DNA/蛋白质序列片段定位、网络数据流中的固定模式检测。

10. 完整 KMP 匹配代码

10.1 使用任意回退表进行匹配

intkmp_search(constchar*text,intn,constchar*pattern,intm,constinttable[]){if(m==0){return0;}inti=0;intj=0;while(i<n&&j<m){if(j==-1||text[i]==pattern[j]){++i;++j;}else{j=table[j];}}return(j==m)?(i-j):-1;}

调用时：

intnext[m];intnextval[m];build_next(pattern,m,next);build_nextval(pattern,m,next,nextval);intpos1=kmp_search(text,n,pattern,m,next);intpos2=kmp_search(text,n,pattern,m,nextval);

pos1与pos2的结果应完全相同，只是比较次数可能不同。

10.2 完整可运行示例

#include<stdio.h>#include<string.h>voidbuild_next(constchar*p,intm,intnext[]){if(m<=0)return;inti=0;intj=-1;next[0]=-1;while(i<m-1){if(j==-1||p[i]==p[j]){++i;++j;next[i]=j;}else{j=next[j];}}}voidbuild_nextval(constchar*p,intm,constintnext[],intnextval[]){if(m<=0)return;nextval[0]=-1;for(intj=1;j<m;++j){intk=next[j];if(k>=0&&p[j]==p[k]){nextval[j]=nextval[k];}else{nextval[j]=k;}}}intkmp_search(constchar*text,intn,constchar*pattern,intm,constinttable[]){if(m==0)return0;inti=0;intj=0;while(i<n&&j<m){if(j==-1||text[i]==pattern[j]){++i;++j;}else{j=table[j];}}return(j==m)?(i-j):-1;}intmain(void){constchar*text="bacbababadababacambabacaddababacasdsd";constchar*pattern="ababaca";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(inti=0;i<m;++i)printf("%d ",next[i]);printf("\\nnextval: ");for(inti=0;i<m;++i)printf("%d ",nextval[i]);intpos=kmp_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: 10

11. 时间复杂度与空间复杂度

11.1 构造数组

• 构造next：O(m)；
• 构造nextval：O(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 1

12.2 LPS 或前缀函数pi

很多算法题使用 LPS（Longest Prefix Suffix）或前缀函数pi：

pi[k] = P[0..k] 的最长相等真前后缀长度

本文next与pi的关系为：

对于 j >= 1：next[j] = pi[j - 1]

因此，看到不同数组时，先检查：

1. 下标从 0 还是 1 开始；
2. 首元素是-1、0还是1；
3. 数组表示“失配后的比较位置”还是“当前前缀的最长 border 长度”；
4. 匹配代码是否与数组定义配套。

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失配时：

1. 普通next令j回退到哪里？
2. 为什么不能直接回退到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. 不同教材数组不同，首先核对下标和哨兵约定。