跳转至

KMP 算法

定义

定义 \(\pi(i)\) 为 \(s(0, i)\) 的最长公共前后缀长度（也叫 border），值得注意的是，这里的前后缀是真前后缀，即这个前后缀不能是字符串本身。（有很多地方将这个数组记为 \(nxt(i)\)，二者其实是同一个东西，不过在公式中用 \(nxt\) 感觉有点怪，因此这里使用 \(\pi\)）

KMP 算法

KMP 算法能够在 \(O(n)\) 的时间内求出 \(\pi(i)\)。

首先，\(\pi(0) = 0\)。假设现在已经求出 \(\pi(i - 1)\)，要求 \(\pi(i)\)。根据 \(\pi\) 的定义，有 \(s(0, \pi(i - 1) - 1) = s(i - \pi(i - 1), i - 1)\)。对于要求的 \(\pi(i)\)，我们希望尽可能地利用之前求过的 \(\pi\) 来更新 \(\pi(i)\)。

一种很理想的情况是 \(s_{\pi(i - 1)} = s_i\)，因为 \(\pi(i - 1)\) 对应的前后缀已经是最长的了，因此 \(\pi(i) = \pi(i - 1) + 1\)。

如果 \(s_{\pi(i - 1)} \ne s_i\)，我们就不能使用 \(\pi(i - 1)\) 更新 \(\pi(i)\) 了。因此，我们希望找到一个 \(s(0, i - 1)\) 的公共前后缀长度仅次于 \(\pi(i - 1)\) 的公共前后缀长度 \(\pi'(i - 1)\)。因为 \(s(0, \pi(i - 1) - 1) = s(i - \pi(i - 1), i - 1)\)，我们要找的 \(\pi'(i - 1)\) 一定满足 \(s(0, \pi'(i - 1) - 1) = s(i - \pi'(i - 1), i - 1) = s(\pi(i - 1) - \pi'(i - 1), \pi(i - 1) - 1)\)，同时我们希望 \(\pi'(i - 1)\) 是仅次于 \(\pi(i - 1)\) 的最大值。可以发现，\(\pi'(i - 1) = \pi(\pi(i - 1) - 1)\)。其中，「仅次于」与 \(\pi\) 定义中的「真前后缀」对应，「最大值」与定义中的「最长」对应（这也是 \(\pi\) 数组「失配指针」名字的由来）。如果此时有 \(s_{\pi'(i - 1)} = s_i\)，那么 \(\pi(i) = \pi'(i - 1)\)，否则，我们需要继续找 \(\pi''(i - 1), \pi^{(3)}(i - 1), \cdots\)，直到 \(\pi^{(k)}(i - 1) = 0\)，此时 \(\pi(i)\) 不能利用之前求过的 \(\pi\) 更新了，需要直接判断 \(s_0\) 是否等于 \(s_i\)。

代码

代码中 nxt 数组即为上文 \(\pi\)。

1
2
3
4
5
6
7
for (int i = 1; i < n; ++i) {
    nxt[i] = nxt[i - 1];
    while (nxt[i] && s[i] != s[nxt[i]])
        nxt[i] = nxt[nxt[i] - 1];
    if (s[i] == s[nxt[i]])
        ++nxt[i];
}

时间复杂度证明

上面的写法并不利于证明时间复杂度，因此我们稍微改变一下形式。

代码

1
2
3
4
5
6
7
for (int i = 1, j = 0; i < n; ++i) {
    while (j && s[i] != s[j])
        j = nxt[j - 1];
    if (s[i] == s[j])
        ++j;
    nxt[i] = j;
}

可以看出，我们只是新增了一个变量 j，算法的执行过程和之前等价。

j 只会在第 \(4 \sim 5\) 行增加，最多增加 \(n\) 次；j 只会在第 \(2 \sim 3\) 行减少，因为最多增加 \(n\) 次，因此最多减少 \(n\) 次。所以内层 while 循环最多执行 \(n\) 次，对于外层循环，只会遍历字符串一次。因此时间复杂度 \(O(n)\)。

应用

字符串匹配

子串匹配

给定两个字符串 \(a, b\)，求 \(a\) 在 \(b\) 中所有出现的位置。

构造一个字符串 \(s = a + \texttt{#} + b\)，其中 \(\texttt{#}\) 是一个 \(a\) 和 \(b\) 中都没有的字符。求出 \(s\) 的 \(\pi\) 数组。接下来从 \(i = 2|a|\) 开始枚举，若 \(\pi(i) = |a|\)，说明 \(a\) 在 \(b\) 的 \(i - 2|a|\) 处出现了。

但是我们发现，由于 \(s_{|a|} = \texttt{#}\)，因此所有的 \(\pi(i)\) 都不会超过 \(|a|\)。由于在匹配过程中，我们仅需要用到 \(\pi(i - 1)\) 和所有 \(i < |a|\) 的 \(\pi(i)\)，因此，我们没必要保存 \(i \geq |a|\) 的 \(\pi(i)\)。具体来说，我们不必显式地将 \(a\) 与 \(b\) 连接起来，只需要先求出 \(|a|\) 的 \(\pi\)，然后使用上文证明时间复杂度时所用的写法求 \(b\) 的 \(\pi\)，只不过不需要保存。如果遇到当前的 \(\pi\) 等于 \(|a|\)，则匹配到了模式串。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
for (int i = 1; i < n; ++i) {
    nxt[i] = nxt[i - 1];
    while (nxt[i] && a[i] != a[nxt[i]])
        nxt[i] = nxt[nxt[i] - 1];
    if (a[i] == a[nxt[i]])
        ++nxt[i];
}
for (int i = 0, tmp = 0; i < m; ++i) {
    while (tmp && b[i] != a[tmp])
        tmp = nxt[tmp - 1];
    if (b[i] == a[tmp])
        ++tmp;
    if (tmp == m) {
        // do something
    }
}

代码中 \(n = |a|, m = |b|\)。

周期

最小周期 1

给定一个字符串 \(s\)，求 \(s\) 的最小周期，最后一个周期可以不完整。

因为 \(\pi(n - 1)\) 是 \(s\) 最长公共前后缀的长度，根据简介中的结论，\(n - \pi(n - 1)\) 是最小周期。

最小周期 2

给定一个字符串 \(s\)，求 \(s\) 的最小周期，最后一个周期必须完整。

此时，最小周期一定是 \(n\) 的因数。因为 \(n - \pi(n - 1)\) 可能不是 \(n\) 的因数，因此我们找到次小周期 \(n - \pi'(n - 1)\)，第三小周期 \(n - \pi^{(2)}(n - 1)\) 等等逐一判断，直到找到一个长度是 \(n\) 因数的周期。