KMP 算法 & KMP 自动机

Border & $\pi$ 函数

一些定义

• 字符串 $S$ 的真前/后缀为非自身的前/后缀。

• 字符串 $S$ 的 border为 $S$ 的公共真前/后缀。

• 字符串 $S$ 的最长 border 为 $\pi$，对于 $S$ 的每个前缀 $S_{1 \sim i}$ 令 $\pi_i$ 为其最长 border，$\pi$ 函数就是所谓的前缀函数。

$\pi$ 函数的性质

• $\forall i,\pi_{i+1}\leqslant \pi_i+1$。

由反证法易知。

• 字符串 $S$ 的所有 border 可以由 $\pi_{|S|}$ 开始不断跳 $\pi$ 由长度从大到小遍历。

只需证明 $S_{1 \sim \pi_{\pi_n}}$ 是 $S$ 的次长 border 即可。

由 $\pi$ 的定义易知。

• 相邻前缀函数满足 $\pi_{i + 1} = \max\limits_{T ~ is ~ the ~ border ~ of ~ S_{1 \sim i}, S_{i + 1} = S_{|T| + 1}} |T| + 1$。

使用反证法易知。

$\pi$ 函数的线性求法

有了上述几条性质，我们可以得到一个求解 $\pi$ 函数的算法：

pi[0] = -1;
for (int i = 1; i <= n; i++)
    for (int j = pi[i - 1]; j >= 0; j = pi[j])
        if (s[j + 1] == s[i]) { pi[i] = j + 1; break; }

直观感受上这个做法是 $\Theta(n ^ 2)$ 的，但实际上它是线性的，复杂度证明如下：

不难发现复杂度来源在于跳 $\pi$，下面我们将证明跳 $\pi$ 的总次数是线性的。

注意 $\pi_i$ 的位置变化情况，不难发现 $\pi_i$ 只会每次 $+1$ 或往前跳若干次，但往前跳的的总距离不能超过当前 $+1$ 的次数，故总路程也是线性的。

$\pi$ 函数的基本应用

字符串匹配

求解模式串 $T$ 在匹配串 $S$ 中的出现位置的问题。

构造一个新的字符串 $T\circ S$，其中 $\circ\not\in S\cup T$，它仅作为一个分隔符。

对这个新的字符串求其 $\pi$ 函数，不难发现由于分隔符的出现，$\forall i, \pi_i \leqslant |T|$，于是找到 $\pi_i = |T|$ 的位置，$i - |T| + 1 \sim i$ 就是一个匹配。

以上即为 $\rm KMP$ 算法。

统计每个前缀的出现次数

考虑到如果某个前缀在之后的位置里出现过，那么一定是某个前缀的 border，于是我们考虑在每个数的最大 border 处统计答案，其为更小 border 的重复次数，并且更小的 border 一定可以通过跳 $\pi$ 遍历到，这样只需要从后往前扫一遍，复杂度 $\Theta(n)$。

for (int i = 1; i <= n; i++) ans[i] = 1;
for (int i = n; i >= 1; i--) ans[pi[i]] += ans[i];

至于这个问题的加强版，统计 $S$ 中的每个前缀在 $T$ 中的出现次数，可以构造 $S\#T$，赋初值的时候只需要将 $T$ 中的位置初始化为 $1$ 即可。

统计本质不同子串的数目

考虑迭代计算，问题转化成：在当前字符串的末尾加入一个新的字符，以这个字符结尾的后缀中有多少个是前面没有出现过的。

如果一个子串 $S_{i\sim n}$ 在前面出现过，则 $\forall j\geqslant i,S_{j\sim n}$ 都在前面出现过。

由反证法易知。

于是就只需求出加入新字符后的串的反串中的 $\max\pi$ 即可，而这个字符的贡献就是 $|S|+1-\max\pi$，时间复杂度 $\Theta(n^2)$。

字符串周期相关性质

称 $k$ 为 $S$ 的一个周期且仅当 $\forall i\leqslant |S|-k, S_i = S_{i + k}$，特别地若 $k \nmid S$ 则称 $k$ 为 $S$ 的弱周期。

• 若字符串 $S$ 存在一个 border $T$，当且仅当 $S$ 存在一个长度为 $|S| - |T|$ 的（弱）周期。

必要性显然，充分性递归论证即可。

• 字符串 $S$ 的最短（弱）周期长度为 $n - \pi_n$。

由 $\pi$ 函数的定义易知。

• 若长度不小于 $p + q$ 的字符串 $S$ 存在长度分别为 $p, q$ 的（弱）周期，那么 $\gcd(p, q)$ 也是 $S$ 的一个（弱）周期。

下面首先证明 $p - q(p > q)$ 也是 $S$ 的一个（弱）周期。

分两种情况讨论：

1. 若 $i \leqslant q$，则 $S_i = S_{i + p} = S_{i + p - q}$，可知 $\forall i \leqslant q, p - q$ 是其一个（弱）周期。

2. 若 $i > q$，则 $S_i = S_{i - q} = S_{i + p - q}$，可知 $\forall i > q, p - q$ 是其一个（弱）周期。

证明 $p - q$ 是 $S$ 的一个（弱）周期后，根据更相减损术的性质，最终可以迭代至 $\gcd(p, q)$ 是 $S$ 的一个（弱）周期。

• 所有强周期的长度均为最短强周期长度的倍数。

若存在一个强周期 $x$，显然有 $x\mid n$，若 $n-\pi_n\nmid x$，则 $\gcd(n-\pi_n,x)<n-\pi_n$ 也为一个强周期，与 $n-\pi_n$ 是最小强周期矛盾。

• 字符串 $S$ 存在周期当且仅当 $n - \pi_n$ 为一个周期。

必要性显然。若存在强周期 $x\mid n$，又因为 $n-\pi_n\mid x$，则 $n-\pi_n\mid n$，充分性得证。

KMP 自动机

在求 $\pi$ 函数的时候，我们发现这个做法是支持在线插入一个字符在末尾并计算函数值的。

并且在做 $\rm KMP$ 的过程中我们发现，在匹配串每一位求 $\pi$ 函数时，并不关心之前匹配串的字符是什么，只关心之前的 $\pi$ 函数值和当前位的字符。

这意味着可以对一个模式串建立一个自动机，结点 $i$ 表示当前节点的 $\pi$ 值为 $i$，新加入一个节点的出边 $c$ 指向跳 $\pi$ 时第一个能够匹配的结点。暴力建这个自动机的复杂度为 $\Theta(n^2|\Sigma|)$，因为出边需要遍历 $\Sigma$，所以不存在求 $\pi$ 函数时指针单方向移动的性质。

但是实际上之前已经计算了从所有节点开始，以任意一个字符为出边会到哪个节点，故可以直接调用。具体规则为，记 $f_{i,c}$ 表示从 $i$ 号节点开始，字符 $c$ 会到达的节点。如果当前到达了节点 $i$ ，字符为 $c$，则如果 $c=s_{i+1}$，那么当前节点指向 $i+1$，否则指向 $f_{\pi_i,c}$。时间复杂度 $\Theta(n|\Sigma|)$。

同 $\rm KMP$ 算法一样，$\rm KMP$ 自动机也可以用来实现若干文本串和模式串的匹配，文本串从节点 $0$ 开始走，每次走到 $|S|$ 都完成了一次匹配。若模式串长度为 $m$，文本串长度为 $n$，数量为 $t$，则时间复杂度为 $\Theta(m+tn|\Sigma|)$。

另一方面，$\rm KMP$ 自动机在完成普通字符串匹配时表现并不优秀，但它可以求解一些特殊的字符串匹配问题，如：

定义 $g_1="a"$，$g_2="aba"$，$g_3="abacaba"\cdots \forall i,g_i=g_{i-1}+(char)i+g_{i-1}$。 给定另一字符串 $S$ 和整数 $k$，求 $S$ 在 $g_k$ 中的匹配次数。保证 $|S|\times k\leqslant 10^6$。

显然题目是要求从 $0$ 号节点开始对 $g_k$ 进行匹配，经过 $|S|$ 号节点的次数是多少。

首先对 $S$ 建立 $\rm KMP$ 自动机，记 $f_{i,j}$ 表示从 $i$ 号节点开始对 $g_j$ 进行匹配后经过 $|S|$ 号节点的次数。记 $k_{i,S}$ 表示从 $i$ 号节点开始，匹配完字符串 $S=g_i+(char)i$ 后停下来的结点，那么有 ：

$$f_{i,j}=f_{i,j-1}+[k_{i,g_{j-1}+(char)(j-1)}=|S|]+f_{k_{i,g_{j-1}+(char)(j-1)},j-1} $$

总时间复杂度 $\Theta(|S|\times k)$。

另外，由于单次添加结点的复杂度是严格 $\Theta(|\Sigma|)$ 的，所以可以对 $\rm KMP$ 自动机进行可持久化处理，总时间复杂度 $\Theta(n|\Sigma|\log n)$。

例题：[CF808G] Anthem of Berland

考虑对模式串建立 $\rm KMP$ 自动机。

令 $f_{i,j}$ 表示对字符串匹配到第 $i$ 位时，跳到自动机的 $j$ 号点匹配的次数最大值，显然有转移：

$$f_{i,to}=\begin{cases}\max\{f_{i-1,j}+[to=m]\}(s_i\not =~'?')\\\max\limits_{k=0}^{25}\{f_{i-1,j}+[to=m]\}(s_i=~'?')\end{cases} $$

由于 $\rm DP$ 空间开不下，需要使用滚动数组。

时间复杂度 $\Theta(|S||T||\Sigma|)$。