next 数组的含义#

next[j] 表示：当模式串第 j 个字符与主串失配时，模式串应回退到第 next[j] 个字符继续比较。

手工求解步骤#

对模式串 T[1..j-1]（即第 j 个字符之前的子串），找其最长相等前后缀的长度 k，则 next[j] = k + 1。

特别规定：next[1] = 0（第 1 个字符就失配，表示主串 i 要后移，模式串从头开始）。

手工求解口诀：看第 j 个字符前面的子串，找最长相等前后缀长度，加 1 就是 next[j]。

求解示例#

以模式串 T = "abaabcac"（下标从 1 开始）为例：

最终结果：next[] = {0, 1, 1, 2, 2, 3, 1, 2}

两种定义的辨析#

做题时务必先看清楚题目用的是哪种定义，否则整个数组会错位。

代码实现#

1
// 求 next 数组（串下标从 1 开始）
2
void getNext(char T[], int next[], int m) {
3
    int j = 1, k = 0;
4
    next[1] = 0;
5
    while (j < m) {
6
        if (k == 0 || T[j] == T[k]) {
7
            j++;
8
            k++;
9
            next[j] = k;
10
        } else {
11
            k = next[k];  // k 回退（核心步骤）
12
        }
13
    }
14
}

代码要点：

• k == 0 表示已退无可退，next[j+1] = 1
• T[j] == T[k] 表示前后缀可以扩展一位，next[j+1] = k+1
• k = next[k] 是利用已有 next 值进行回退，这一步骤的思想和 KMP 匹配过程完全一致

KMP 匹配过程#

1
int KMP(char S[], char T[], int next[], int n, int m) {
2
    int i = 1, j = 1;
3
    while (i <= n && j <= m) {
4
        if (j == 0 || S[i] == T[j]) {
5
            i++;
6
            j++;
7
        } else {
8
            j = next[j];  // 主串 i 不回溯，模式串 j 回退
9
        }
10
    }
11
    if (j > m) return i - m;
12
    return -1;
13
}

匹配过程关键点：

1. j == 0 时说明模式串第 1 个字符就失配，此时 i++, j++（主串后移一位，模式串从头开始）
2. S[i] == T[j] 时两个指针同时后移
3. 失配时 j = next[j]，模式串右滑，跳过不可能匹配的位置

为什么需要 nextval#

next 数组存在一个问题：如果 T[j] == T[next[j]]，那么回退到 next[j] 后必然还是失配（因为和同一个字符比较），造成多余比较。

手工求 nextval（考研常考）#

先求出 next 数组，再逐个修正：对每个 j，若 T[j] == T[next[j]]，则 nextval[j] = nextval[next[j]]；否则 nextval[j] = next[j]。

以 T = "abaabcac" 为例：

最终结果：nextval[] = {0, 1, 0, 2, 1, 3, 0, 2}

代码实现#

1
void getNextval(char T[], int nextval[], int m) {
2
    int j = 1, k = 0;
3
    nextval[1] = 0;
4
    while (j < m) {
5
        if (k == 0 || T[j] == T[k]) {
6
            j++;
7
            k++;
8
            if (T[j] != T[k])
9
                nextval[j] = k;
10
            else
11
                nextval[j] = nextval[k];  // 相等则继续回退
12
        } else {
13
            k = nextval[k];
14
        }
15
    }
16
}