KMP算法

2024-12-17

字数统计: 2.1k字 | 阅读时长: 8分

前言

KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配（在字符串中查找子串）的高效算法，由Donald Knuth、Vaughan Pratt 和 James H. Morris 独立发明，并在1977年被共同发表。它改进了朴素字符串匹配算法，在最坏情况下的时间复杂度为 $O(n + m)$，其中 $n$ 是文本字符串的长度，$m$ 是模式字符串的长度。

子串、子序列、真前缀和真后缀

子串：子串是由字符串中连续字符组成的新字符串。
子序列：子序列是通过删除字符串中某些字符而不改变其余字符顺序得到的序列。
真前缀：真前缀是指字符串的非空开头部分，不包括整个字符串本身。
真后缀：真后缀是指字符串的非空结尾部分，同样不包括整个字符串本身。

前缀函数

给定一个长度为 $n$ 的字符串 $s$，其前缀函数被定义为一个长度为 $n$ 的数组 $\pi$。其中 $\pi[i]$ 的定义是：

如果子串 $s[0\dots i]$ 有一对相等的真前缀与真后缀：$s[0\dots k-1]$ 和 $s[i - (k - 1) \dots i]$，那么 $\pi[i]$ 就是这个相等的真前缀（或者真后缀，因为它们相等）的长度，也就是 $\pi[i]=k$；
如果不止有一对相等的，那么 $\pi[i]$ 就是其中最长的那一对的长度；
如果没有相等的，那么 $\pi[i]=0$。

简单来说 $\pi[i]$ 就是，子串 $s[0\dots i]$ 最长的相等的真前缀与真后缀的长度。

用数学语言描述如下：

$\pi[i] = \max_{k = 0 \dots i}\{k: s[0 \dots k - 1] = s[i - (k - 1) \dots i]\}$

特别地，规定 $\pi[0]=0$。

举例来说，字符串 $aabaaab$ 的前缀函数为 $[0, 1, 0, 1, 2, 2, 3]$。

1 2	a a b a a a b 0 1 0 1 2 2 3

计算前缀函数的算法

最朴素的算法是双循环遍历，这个很容易想到。这种朴素算法的时间复杂度是$O(n^3)$，因为除去外层的双循环外，比对真前缀和真后缀的相等也需要进行一次遍历。

考虑到当取一个尽可能大的 $\pi[i+1]$ 时，必然要求新增的 $s[i+1]$ 也与之对应的字符匹配，即 $s[i+1]=s[\pi[i]]$, 此时 $\pi[i+1] = \pi[i]+1$。所以当移动到下一个位置时，前缀函数的值要么增加一，要么维持不变，要么减少。则对于位置$i+1$的内部循环的起始位置可以从上一位置的$\pi[i]$开始，此时“内循环”和“子串对比”存在此消彼长的制约关系，即$\pi[i]$限制了求取$\pi[i+1]$的最大内循环次数，则时间复杂度下降至$O(n^2)$。

继续考虑当 $s[i+1] \neq s[\pi[i]]$ 时如何跳转，即对于新指向的位置，在第一次对比时发生了失配。此时希望找到“合适的第二长度$j$”，使得在位置 $i$ 的前缀性质仍得以保持，也即 $s[0 \dots j - 1] = s[i - j + 1 \dots i]$：

$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1}$

如果我们找到了这样的长度 $j$，那么仅需要再次比较 $s[i + 1]$ 和 $s[j]$。如果它们相等，那么就有 $\pi[i + 1] = j + 1$。否则，我们需要找到子串 $s[0\dots i]$ 仅次于 $j$ 的第二长度 $j^{(2)}$，使得前缀性质得以保持，如此反复，直到 $j = 0$。如果 $s[i + 1] \neq s[0]$，则 $\pi[i + 1] = 0$。

可以发现，因为 $s[0\dots \pi[i]-1] = s[i-\pi[i]+1\dots i]$，所以对于 $s[0\dots i]$ 的第二长度 $j$，有这样的性质：

$s[0 \dots j - 1] = s[i - j + 1 \dots i]= s[\pi[i]-j\dots \pi[i]-1]$

也就是说 $j$ 等价于子串 $s[\pi[i]-1]$ 的前缀函数值，即 $j=\pi[\pi[i]-1]$。同理，次于 $j$ 的第二长度等价于 $s[j-1]$ 的前缀函数值，$j^{(2)}=\pi[j-1]$。

显然我们可以得到一个关于 $j$ 的状态转移方程：$j^{(n)}=\pi[j^{(n-1)}-1], \ \ (j^{(n-1)}>0)$。所以最终我们可以构建一个不需要进行任何字符串比较，并且只进行 $O(n)$ 次操作的算法。

static int[] prefix_function(String s) {
    int n = s.length();
    int[] pi = new int[n];
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1]; // 初始化 j
        while (j > 0 && s.charAt(i) != s.charAt(j)) {
            j = pi[j - 1];  // 无法匹配时，找到次长的 j
        }
        if (s.charAt(i) == s.charAt(j)) {
            j++;
        }
        pi[i] = j; // 存储前缀函数值
    }
    return pi;
}

具体的算法优化过程可参考文献[1]。

KMP算法

KMP算法用于在字符串中查找子串，该任务是前缀函数的一个典型应用。

给定一个文本 $t$ 和一个字符串 $s$，我们尝试找到并展示 $s$ 在 $t$ 中的所有出现（occurrence）。

为了简便起见，我们用 $n$ 表示字符串 $s$ 的长度，用 $m$ 表示文本 $t$ 的长度。

我们构造一个字符串 $s + # + t$，其中 $#$ 为一个既不出现在 $s$ 中也不出现在 $t$ 中的分隔符。接下来计算该字符串的前缀函数。现在考虑该前缀函数除去最开始 $n + 1$ 个值（即属于字符串 $s$ 和分隔符的函数值）后其余函数值的意义。根据定义，$\pi[i]$ 为右端点在 $i$ 且同时为一个前缀的最长真子串的长度，具体到我们的这种情况下，其值为与 $s$ 的前缀相同且右端点位于 $i$ 的最长子串的长度。由于分隔符的存在，该长度不可能超过 $n$。而如果等式 $\pi[i] = n$ 成立，则意味着 $s$ 完整出现在该位置（即其右端点位于位置 $i$）。注意该位置的下标是对字符串 $s + # + t$ 而言的。

因此如果在某一位置 $i$ 有 $\pi[i] = n$ 成立，则字符串 $s$ 在字符串 $t$ 的 $i - (n - 1) - (n + 1) = i - 2n$ 处出现。

可以先根据以上原理，写出用 $O(n + m)$ 的时间以及 $O(n + m)$ 的内存解决该问题的代码如下。注意$O$符号描述的是当输入规模趋向于无穷大时算法性能的上界，它忽略常数因子。

static List<Integer> find_occurrences(String text, String pattern) {
    String cur = pattern + '#' + text;
    int sz1 = text.length(), sz2 = pattern.length();
    List<Integer> v = new ArrayList<>();
    int[] lps = prefix_function(cur);
    for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
        if (lps[i] == sz2) {
            v.add(i - 2 * sz2);
        }
    }
    return v;
}

如果我们知道前缀函数的值永远不超过一特定值（即模式串的长度），那么我们不需要存储整个字符串以及整个前缀函数，而只需要存储字符串 $ s + #$ 以及相应的前缀函数值即可。我们可以一次读入字符串 $t$ 的一个字符并计算当前位置的前缀函数值。可以更新代码如下。

static List<Integer> find_occurrences(String text, String pattern) {
    // 计算模式串加上分隔符的前缀函数
    String cur = pattern + '#';
    int[] lps = prefix_function(cur);
    
    List<Integer> v = new ArrayList<>();
    int sz1 = text.length(), sz2 = pattern.length();
    int q = 0; // 在模式串上进行匹配的位置指针

    // 遍历文本串的每一个字符
    for (int i = 0; i < sz1; ++i) {
        // 如果不匹配并且 q > 0，则回溯到之前的一个可能匹配点继续尝试匹配
        while (q > 0 && pattern.charAt(q) != text.charAt(i)) {
            q = lps[q - 1];
        }
        // 如果匹配成功，则增加 q
        if (pattern.charAt(q) == text.charAt(i)) {
            q++;
        }
        // 如果 q 达到了模式串的长度，说明找到了一个完整匹配
        if (q == sz2) {
            // 找到了一个匹配，记录匹配的起始位置
            v.add(i - sz2 + 1);
            // 准备找下一个匹配
            q = lps[q - 1];
        }
    }
    return v;
}

因此 Knuth–Morris–Pratt 算法（简称 KMP 算法）用 $O(n + m)$ 的时间以及 $O(n)$ 的内存解决了该问题。

参考文献

[1] https://oi-wiki.org/string/kmp/

后记

首发于 silencezheng.top，转载请注明出处。