跳到主要内容

十、KMP算法的进一步优化（求 nextval 数组）

NextVal 数组求解：自定义演练​

NextVal 是对 Next 数组的修正。 核心优化点：如果当前字符 T[i] 和它要回溯到的字符 T[j] 相等，那么回溯是徒劳的（因为 T[j] 肯定也不匹配）。此时我们直接让 T[i] 继承 T[j] 的回溯位置。

动手试试
  1. 输入 ababaa：观察 nextval[3] 为什么是 0 而不是 1。
  2. 输入 aaaab：你会看到连续的 nextval 都是 0（因为字符全部相同，一直递归优化）。
试一试: "aaaaa" (全优化)
Step 1/19初始化：i=1, j=0, nextval[1]=0
1void get_nextval(String T, int nextval[]) {
2    int i = 1; 
3    int j = 0;
4    nextval[1] = 0;
5    
6    while (i < T.length) {
7        if (j == 0 || T.ch[i] == T.ch[j]) {
8            ++i; ++j;
9            
10            // --- 核心优化逻辑 ---
11            if (T.ch[i] != T.ch[j]) {
12                nextval[i] = j; // 不需要优化
13            } else {
14                // 字符相等，递归引用
15                nextval[i] = nextval[j]; 
16            }
17            // ------------------
18        } else {
19            j = nextval[j]; // 回溯
20        }
21    }
22}
i
a
1
b
2
a
3
b
4
a
5
a
6
nextval:
0
?
?
?
?
?

1. 核心思想​

解决 next 数组中“失配字符与跳转后字符相同”的冗余对比问题，优化跳转效率。

2. 示例代码图解​

nextval[1] = 0;
for (int j = 2;j < T.length;j++) {
    if (T.ch[next[j]] == T.ch[j])
        nextval[j] = nextval[next[j]];
    else
        nextval[j] = next[j];
}

Img 首先默认 nextval[1] = 0,然后继续求后面的 nextval 值;方法:如果当前 next[ j ] 所指向的字符和目前 j 所指的字符他们两个不相等,那我们就让 nextval 的值 = next 的值.

Img 如图:当前 next[2] 指向的字符为1, j = 1时所指向的模式串为a;此时 a≠b;所以 nextval[2]=next[2]=1.

Img 如图:当前 next[3] 指向的字符为1, j = 1时所指向的模式串为a;此时 a=a;所以 nextval[3] = nextval[next[1]] = 0.

Img 如图:当前 next[4] 指向的字符为2, j = 2时所指向的模式串为b;此时 b = b;所以 nextval[4] = nextval[next[2]] = 1.

Img 如图:当前next[5]指向的字符为3, j = 3时所指向的模式串为a;此时a=a;所以nextval[5] = nextval[next[3]] = 0.

Img 如图:当前next[6]指向的字符为4, j = 4时所指向的模式串为b;此时a≠b;所以nextval[6] = next[6] = 4. ————————————————

3. 示例​

next数组: nextval数组:

终极对比：Next vs NextVal​

通过下方的动态演示，你可以直观地看到 NextVal 数组是如何在 Next 数组的基础上进行"再优化"的。

观察指南

绿色格子代表触发了优化逻辑。 输入 aaaaa：你会看到 Next 是 01234，而 NextVal 是 00004（极度优化）。 输入 ababaa：观察第 3 位和第 5 位，为什么 NextVal 会变成 0。

推荐测试: "aaaaa", "ababaa", "aaaab"
Step 1/19初始化：i=1, j=0。next[1]=0, nextval[1]=0
1// KMP Next & NextVal 计算逻辑
2void get_nextval(String T, int next[], int nextval[]) {
3    int i=1, j=0;
4    next[1]=0; nextval[1]=0;
5    
6    while(i < T.length) {
7        if(j==0 || T[i]==T[j]) {
8            ++i; ++j;
9            next[i] = j; // 记录 next
10            
11            // --- NextVal 优化检查 ---
12            if(T[i] != T[j]) 
13                nextval[i] = j; // 无需优化
14            else 
15                nextval[i] = nextval[j]; // 递归优化
16        } else {
17            j = next[j]; // 失配回溯
18        }
19    }
20}
模式串 T
1
a
2
b
3
a
4
b
5
a
6
a
Next
0
-
-
-
-
-
NextVal
0
-
-
-
-
-
触发优化 (NextVal ≠ Next)
当前计算位 (i)

💬 留下你的问题或见解