字符串算法（KMP、Z 函数）

目录¶

KMP 算法
Z 函数（拓展 KMP）

1 KMP 算法¶

1.1 前缀函数¶

定义

给定一个长度为 $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$。

计算前缀函数的高效算法¶

观察可以发现，因为 $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] \]

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

这是一个在线算法，即其当数据到达时处理它——举例来说，你可以一个字符一个字符的读取字符串，立即处理它们以计算出每个字符的前缀函数值。该算法仍然需要存储字符串本身以及先前计算过的前缀函数值，但如果我们已经预先知道该字符串前缀函数的最大可能取值 $M$，那么我们仅需要存储该字符串的前 $M + 1$ 个字符以及对应的前缀函数值。

1.2 在字符串中查找子串：Knuth-Morris-Pratt 算法¶

给定一个文本 $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$ 处出现。

正如在前缀函数的计算中已经提到的那样，如果我们知道前缀函数的值永远不超过一特定值，那么我们不需要存储整个字符串以及整个前缀函数，而只需要二者开头的一部分。在我们这种情况下这意味着只需要存储字符串 $s +$ # 以及相应的前缀函数值即可。我们可以一次读入字符串 $t$ 的一个字符并计算当前位置的前缀函数值。

实现

vector<int> find_occurrences(string text, string pattern) {
    string cur = pattern + '#' + text;
    int sz1 = text.size(), sz2 = pattern.size();
    vector<int> v;
    vector<int> lps = prefix_function(cur);
    for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
        if (lps[i] == sz2) v.push_back(i - 2 * sz2);
    }
    return v;
}

1.3 根据前缀函数构建一个自动机¶

让我们重新回到通过一个分隔符将两个字符串拼接的新字符串。对于字符串 $s$ 和 $t$ 我们计算 $s +$ # $+ t$ 的前缀函数。显然，因为 # 是一个分隔符，前缀函数值永远不会超过 $|s|$。因此我们只需要存储字符串 $s +$ # 和其对应的前缀函数值，之后就可以动态计算对于之后所有字符的前缀函数值：

实际上在这种情况下，知道 $t$ 的下一个字符 $c$ 以及之前位置的前缀函数值便足以计算下一个位置的前缀函数值，而不需要用到任何其它 $t$ 的字符和对应的前缀函数值。

换句话说，我们可以构造一个 自动机（一个有限状态机）：其状态为当前的前缀函数值，而从一个状态到另一个状态的转移则由下一个字符确定。

因此，即使没有字符串 $t$，我们同样可以应用构造转移表的算法构造一个转移表 $(\text{old}\ \pi, c) \rightarrow \text{new}\_\pi$：

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int j = i;
            while (j > 0 && 'a' + c != s[j]) j = pi[j - 1];
            if ('a' + c == s[j]) j++;
            aut[i][c] = j;
        }
    }
}

然而在这种形式下，对于小写字母表，算法的时间复杂度为 $O(|\Sigma|n^2)$。注意到我们可以应用动态规划来利用表中已计算过的部分。只要我们从值 $j$ 变化到 $\pi[j - 1]$，那么我们实际上在说转移 $(j, c)$ 所到达的状态同转移 $(\pi[j - 1], c)$ 一样，但该答案我们之前已经精确计算过了。

优化实现

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'a' + c != s[i])
                aut[i][c] = aut[pi[i - 1]][c];
            else
                aut[i][c] = i + ('a' + c == s[i]);
        }
    }
}

最终我们可在 $O(|\Sigma|n)$ 的时间复杂度内构造该自动机。

该自动机在什么时候有用呢？首先，记得大部分时候我们为了一个目的使用字符串 $s +$ # $+ t$ 的前缀函数：寻找字符串 $s$ 在字符串 $t$ 中的所有出现。

因此使用该自动机的最直接的好处是加速计算字符串 $s +$ # $+ t$ 的前缀函数。

通过构建 $s +$ # 的自动机，我们不再需要存储字符串 $s$ 以及其对应的前缀函数值。所有转移已经在表中计算过了。

但除此以外，还有第二个不那么直接的应用。我们可以在字符串 $t$ 是 某些通过一些规则构造的巨型字符串 时，使用该自动机加速计算。Gray 字符串，或者一个由一些短的输入串的递归组合所构造的字符串都是这种例子。

2 Z 函数（拓展 KMP）¶

约定：字符串下标以 $0$ 起点。

2.1 定义¶

对于一个长度为 $n$ 的字符串 $s$，定义函数 $z[i]$ 表示 $s$ 和 $s[i, n-1]$（即以 $s[i]$ 开头的后缀）的最长公共前缀（LCP）的长度，则 $z$ 被称为 $s$ 的 Z 函数。特别地，$z[0] = 0$。

2.2 线性算法¶

如同大多数字符串主题所介绍的算法，其关键在于，运用自动机的思想寻找限制条件下的状态转移函数，使得可以借助之前的状态来加速计算新的状态。

在该算法中，我们从 $1$ 到 $n-1$ 顺次计算 $z[i]$ 的值（$z[0] = 0$）。在计算 $z[i]$ 的过程中，我们会利用已经计算好的 $z[0],\dots, z[i-1]$。

对于 $i$，我们称区间 $[i, i + z[i] - 1]$ 是 $i$ 的 匹配段，也可以叫 Z-box。

算法的过程中我们维护右端点最靠右的匹配段。为了方便，记作 $[l, r]$。根据定义，$s[l, r]$ 是 $s$ 的前缀。在计算 $z[i]$ 时我们保证 $l \leq i$。初始时 $l = r = 0$。

在计算 $z[i]$ 的过程中：

如果 $i \leq r$，那么根据 $[l, r]$ 的定义有 $s[i, r]=s[i - l, r - l]$（$s[0, r - l] = s[l, r]$），因此 $z[i] \geq \min(z[i - l], r - i + 1)$。此时：
- 若 $z[i - l] < r - i + 1$，则 $z[i] = z[i - l]$。
- 否则 $z[i - l] \geq r - i + 1$，这时我们令 $z[i] = r - i + 1$，然后暴力枚举下一个字符扩展 $z[i]$ 直到不能扩展为止。
如果 $i > r$，那么我们直接按照朴素算法，从 $s[i]$ 开始比较，暴力求出 $z[i]$。
在求出 $z[i]$ 后，如果 $i + z[i] - 1 > r$，我们就需要更新 $[l,r]$，即令 $l = i, r = i + z[i] - 1$。

vector<int> z_function(string s) {
    int n = (int)s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r && z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        } else {
            z[i] = max(0, r - i + 1);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        }
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}

另一种常数大一些的写法：

vector<int> z_function(string s) {
    int n = (int)s.length();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r) z[i] = min(z[i - l], r - i + 1);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}

def z_function(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r and z[i - l] < r - i + 1:
            z[i] = z[i - l]
        else:
            z[i] = max(0, r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

2.3 复杂度分析¶

对于内层 while 循环，每次执行都会使得 $r$ 向后移动至少 $1$ 位，而 $r < n - 1$，所以总共只会执行 $n$ 次。

对于外层循环，只有一遍线性遍历。

总复杂度为 $O(n)$。

总结¶

算法	时间复杂度	空间复杂度	应用场景
前缀函数	$O(n)$	$O(n)$	KMP 核心
KMP 匹配	$O(n+m)$	$O(n)$	子串查找
自动机	$O(	\Sigma	n)$
Z 函数	$O(n)$	$O(n)$	后缀与前缀匹配

算法	时间复杂度	空间复杂度	应用场景
前缀函数	\(O(n)\)	\(O(n)\)	KMP 核心
KMP 匹配	\(O(n+m)\)	\(O(n)\)	子串查找
自动机	$O(	\Sigma	n)$
Z 函数	\(O(n)\)	\(O(n)\)	后缀与前缀匹配