字符串匹配 - KMP 算法

KMP 算法 是用来在字符串中搜索一个子字符串的算法。

本文内容较多，需要读者静心阅读。

在长度为 n 的字符串 s 中搜索长度为 m 的子串 p 的位置。

本文以 ABCDABCABCABABCABCDA 为主串 ， ABCABCD 为子串。

易知，简单匹配方法如下：

• 将子串 p 依次对齐到 s 的每个字符的位置。
• 迭代子串进行比对，如果全部匹配，则完成匹配。

此方法的代码省略，其时间复杂度是 $O(m * n)$ 。

将上面简单匹配的过程展开，如下图 1.1 所示，其中绿色的部分表示字符比对成功，红色表示比对失败 。 图中每一次比对，都会将子串 p 右移一位，然后子串从头开始匹配。

下面将考虑如何减少比对的次数。

考虑第一次失配的状态，如下图 1.2 所示，此时绿色的部分是目前匹配成功的部分。

将说明，接下来的两次比对，可以跳过。

原因在于，右移后的重叠部分 overlap 都无法匹配，整个子串 p 就不必比对了。

下面考虑第二次失配的状态，如下图 1.4 所示，同样的思路可以知道，中间的两次比对可以跳过。

原因仍然在于，因为重叠部分 overlap 无法匹配，整个子串 p 必然无法匹配。

但是，下面一次移动，就无法如此断言。因为重叠部分 overlap 是匹配的，意味着尾端的 ABC 有可能作为下一次比对的开头，那么有必要进行进一步的比对。

以上所说的重叠部分 overlap 是什么？

在刚刚失配时，假设已经匹配成功的部分是 p' ，它是 p 的一个子串， 那么重叠部分是 p' 尾部 和 右移 p' 后的头部交叉：

如果 p' 的尾部和头部是无重叠的，则可以开心地跳跃 len(p') 个字符。否则，如果 p' 的尾巴和头有匹配的部分，假如匹配了 len(overlap) 个字符， 那么只可以向右跳跃 len(p') - len(overlap) 个字符。

按照这个结论，算法过程优化为下图的样子：

此外，因为重叠部分 overlap 已经是匹配的，所以，移动 p 后，不必回溯到 p 的起点再去匹配一次，直接从失配处继续匹配即可。

如此，最终的算法过程则是下图的样子，可以看到，主串 s 的遍历无需回溯，只需要在失配的时候回溯子串就好了。

而子串回溯时， j 应该跳到的位置，恰好可以用已经匹配好的子串 p' 的头尾重叠部分的长度 len(overlap) 来表达：

接下来讨论，如何求解重叠部分的长度。

现在的问题是，对于子串 p 的每一个前缀子串 p' ，如何找到它的头部和尾部的重叠部分的长度？

我们观察一下本文例子中的 p' 的情况和对应的 overlap 长度。 下图 2.1 中左边的是 p 的每一个前缀子串，右边是头尾重叠部分的长度：

采用归纳法分析， 假设 p'(k) 表示长度为 k 的子串，其重叠部分长度为 len(k) 。 我们考虑对它的右面新增一个字符，形成新的子串 p'(k+1) ：

• 如果新增的字符和原来重叠部分后的字符相同，那么： len(k+1) = len(k) + 1 ，如下图 2.2 所示：

  图 2.2 - 新增一个字符 C 后，重叠部分变长

• 否则，新的子串没有形成头尾重叠， len(k+1) = 0 。

  图 2.3 - 新增一个字符 C 后，重叠部分消失的情况

其中，用来和新增的字符对比的元素 （上图 2.2 和 2.3 中的 左边的 C ）的位置，是 len(k) ，对应的元素为 p'(k)[len(k)] 。

这样就形成了递推关系，这里所说的 len(k) 就是常说的 next 数组，它指明了失配时，子串回溯的目标位置。

从算法的总体过程可以看出：

• 预处理过程

  共有 m 个前缀子串，因此时间复杂度 O(m) 。

• 查找过程

  由可知，查找过程的迭代次数 = i 迭代次数 + 失配次数。因为主串不回溯，失配时， j 回溯后会再原地匹配一次。 即 n + 失配次数 小于 2n 。

总体的时间复杂度则为 O(2n + m) 即 O(n + m) ，因 m < n ，也可说时间复杂度是 O(n) 。

// ComputeNext 为长度为 m 的模式串 p 计算 next 数组.
// next 数组的含义：
// 取字符串 p 的位置 j 之前的前缀字符串 p' ，其头尾的最大公共长度即 next[j]
// 此处采用递推方法实现
void ComputeNext(char *p, int m, int next[]) {
    next[0] = 0;
    if (m <= 1) return;

    // p' 是单个字符时，认为它无公共头尾
    next[1] = 0;

    // j 是 next 数组的第 j 项
    // p' 是字符串 p 的长度为 j 的子串
    int j = 2;

    while (j < m) {
        if (p[j - 1] == p[next[j - 1]]) {
            next[j] = next[j - 1] + 1;
        } else {
            next[j] = 0;
        }

        j++;
    }
}

// KMP 从长度为 n 的字符串 s 中查找长度为 m 的字符串 p ，返回其位置.
// 找不到则返回 -1
int KMP(char *s, int n, char *p, int m) {
    // 预处理 next 数组
    int next[m];
    ComputeNext(p, m, next);

    // i 遍历 s
    // j 遍历 p
    int i = 0;
    int j = 0;

    while (i < n) {
        // 匹配
        if (s[i] == p[j]) {
            if (j == m - 1) {
                // 子串匹配到尾部，说明命中
                // 返回匹配的起始位置
                return i + 1 - m;
            } else {
                // 否则，则继续匹配
                i++;
                j++;
            }
        } else {
            if (j == 0) {
                // j 已经在串首, 说明第一个字符不匹配
                // 不必再回溯子串，主串迭代进 1
                i++;
            } else {
                // 失配，j 回溯
                // 回溯的目标位置，已经匹配到的子串的头尾公共部分的长度处
                j = next[j];
            }
        }
    }

    return -1;  // 查找失败
}

（完）