4.2 KMP 算法

利用部分匹配信息让主串指针不回溯——从最长相等前后缀出发，手算与机算 next、nextval 数组。

从朴素算法的浪费说起

在主串 S = 'ababcabcacbab' 中查找 T = 'abcac'。朴素算法第三趟时，S[3..6] = 'abca' 已经与 T[1..4] 匹配，在 T[5] 处失配：

朴素算法接下来会把 i 回溯到 4，依次尝试 T 对齐 S[4]、S[5]……但其实根据已匹配的 'abca' 就能判断：对齐 S[4]（b）和 S[5]（c）都不可能成功，因为它们与 T[1] = 'a' 不等。唯一有希望的是把 T[1] 对齐 S[6]（'abca' 的最后一个 a），而且这个 a 已经比较过了，可以直接从 T[2] 与 S[7] 开始比较。

这就是 KMP 算法的思想：主串指针 i 永不回溯，失配时只把模式串向右滑动到合适位置，滑动的距离只取决于模式串本身。

前缀、后缀与部分匹配值

• 前缀：除最后一个字符外，字符串的所有头部子串；
• 后缀：除第一个字符外，字符串的所有尾部子串；
• 部分匹配值（PM）：字符串的前缀和后缀的最长相等前后缀长度。

以 'ababa' 为例：前缀有 {a, ab, aba, abab}，后缀有 {a, ba, aba, baba}，最长相等前后缀为 'aba'，部分匹配值为 3。

对模式串 'abcac' 的每个前缀子串求部分匹配值：

由 PM 推出移动位数与 next

当 T[j] 失配时，已匹配的是 T[1..j−1]，设其部分匹配值为 $\mathrm{PM}(j-1)$，则：

右移之后，模式串中下一个与 S[i] 比较的位置为

即：next[j] = T[1..j−1] 的最长相等前后缀长度 + 1。特别地，规定 next[1] = 0，表示”模式串第一个字符就失配了，此时主串指针应后移一位，模式串从头开始”。

于是 'abcac' 的 next 数组为 [0, 1, 1, 1, 2]。

KMP 匹配过程

1int Index_KMP(SString S, SString T, int next[]) {
2    int i = 1, j = 1;
3    while (i <= S.length && j <= T.length) {
4        if (j == 0 || S.ch[i] == T.ch[j]) {
5            ++i; ++j;            // 继续比较后继字符
6        } else {
7            j = next[j];         // 主串 i 不回溯，模式串右滑
8        }
9    }
10    if (j > T.length) return i - T.length;
11    else return 0;
12}

对比上一课的朴素匹配，注意观察：

• 失配时 i 不动，只有 j = next[j]；
• j == 0 时（模式串第 1 个字符就失配），i 和 j 同时加 1。

机算 next 数组

next 的求法本身也是一个”模式串自己匹配自己”的过程。已知 next[i] = j，即 T[1..j−1] 是 T[1..i−1] 的最长相等前后缀，求 next[i+1]：

• 若 T[i] == T[j]：最长相等前后缀可以延长一位，next[i+1] = j + 1；
• 若 T[i] != T[j]：把”前缀”T[1..j] 看成新的模式串，令 j = next[j] 继续比较，直到找到相等的字符或 j == 0。

1void get_next(SString T, int next[]) {
2    int i = 1, j = 0;
3    next[1] = 0;
4    while (i < T.length) {
5        if (j == 0 || T.ch[i] == T.ch[j]) {
6            ++i; ++j;
7            next[i] = j;         // 若 pi == pj，则 next[i+1] = next[i] + 1
8        } else {
9            j = next[j];         // 否则令 j = next[j]，继续寻找
10        }
11    }
12}

优化：nextval 数组

考虑模式串 'aaaab'，其 next 数组为 [0, 1, 2, 3, 4]。若与主串 'aaabaaaab' 匹配，在 T[4] 失配（主串字符为 b）后，j 会依次变为 3、2、1——但 T[3] = T[2] = T[1] = 'a'，都与 T[4] 相同，必然会再次失配，这些比较毫无意义。

改进思路：如果 T[j] == T[next[j]]，就把 next[j] 修正为 next[next[j]]，直到两者不相等为止，修正后的数组称为 nextval。

手算 nextval 的方法：从左往右，nextval[1] = 0；对 j ≥ 2，若 T[j] ≠ T[next[j]]，则 nextval[j] = next[j]；否则 nextval[j] = nextval[next[j]]。

1void get_nextval(SString T, int nextval[]) {
2    int i = 1, j = 0;
3    nextval[1] = 0;
4    while (i < T.length) {
5        if (j == 0 || T.ch[i] == T.ch[j]) {
6            ++i; ++j;
7            if (T.ch[i] != T.ch[j]) nextval[i] = j;
8            else nextval[i] = nextval[j];   // 相同则继续"递归"
9        } else {
10            j = nextval[j];
11        }
12    }
13}

复杂度

• 求 next 数组：$O(m)$；KMP 匹配：$O(n)$；总时间复杂度 $O(n + m)$。
• 朴素算法在一般情况下的实际执行时间也接近 $O(n + m)$，因此至今仍被广泛采用。KMP 算法仅在主串与子串有很多”部分匹配”时才显得比朴素算法快得多，其主要优点是主串不回溯。

即时练习