字符串 - KMP

Border

设 $S$ 为字符串，用 $S[l,r]$ 表示 $S_lS_{l+1}\cdots S_r$ 组成的子串，用 $|S|$ 表示它的长度。

如果对整数 $p$ 满足 $S[1,p]=S[|S|-p+1,|S|]$ 那么称 $p$ 为 $S$ 的一个 $\text{Border}$。

特殊地，$p=0$ 和 $p=|S|$ 都是 $S$ 的 $\text{Border}$。

例如，$S=\texttt{abbacabb}$，那么 $p=8,3,0$ 是它的所有 $\text{Border}$。

如果整数 $q$ 对所有 $1\le i,i+q\le |S|$ 有 $S_i=S_{i+q}$ 恒成立，则称 $q$ 是 $S$ 的一个周期。

注意这里周期并不一定整除 $|S|$，例如 $S=\texttt{abcabcab}$，那么 $q=3$ 是一个周期。

如果我们把 $\text{Border}$ 的定义改成这种形式，会是：

如果整数 $p$ 对所有 $1\le i,i+|S|-p\le |S|$ 有 $S_i=S_{i+|S|-p}$ 恒成立，则称 $p$ 是 $S$ 的一个 $\text{Border}$。

因此每个 $p$ 对应一个 $|S|-p$ 是字符串的周期。

KMP 算法就是求出每一个前缀 $S[1,i]$ 的最大的小于 $i$ 的 $\text{Border}$。

注意，这里的 $\text{Border}$ 既可以指长度，也可以指对应的那个字符串，根据语境确定是哪个意思。

KMP

我们可以发现，对于前缀 $S[1,i]$ 的所有 $\text{Border}$，扣掉最后一个字母后，一定是 $S[1,i-1]$ 的 $\text{Border}$。

所以我们可以从大到小遍历 $S[1,i-1]$ 的所有 $\text{Border}$，验证加一个字母后是不是 $S[1,i]$ 的 $\text{Border}$，如果是的话就求出来了。

定义 $\text{next}(i)$ 表示 $S[1,i]$ 的最大的小于 $i$ 的 $\text{Border}$，有这样一个结论：对于 $S[1,i]$ 的所有长度小于 $i$ 的 $\text{Border}$，都可以通过跳 $\text{next}(\text{next}(\cdots\text{next}(i)))$ 获得到。

证明：如果 $p$ 是 $S[1,i]$ 的 $\text{Border}$，$q(q>p)$ 也是 $S[1,i]$ 的 $\text{Border}$，那么 $p$ 是 $q$ 的 $\text{Border}$。因此将 $S[1,i]$ 的所有 $\text{Border}$ 排序，不妨设为 $i>p_1>p_2>\dots>0$ ，那么显然有 $p_k$ 是 $p_{k-1}$ 的最大 $\text{Border}$，因此可以通过跳 $\text{next}$ 获得到所有 $\text{Border}$。

因此我们的代码写出来应当像是这个样子：

n = len(s)
nxt[1] = 0
for i = 2 to n:
    nxt[i] = nxt[i-1]
    while nxt[i] != 0 and s[i] != s[nxt[i] + 1]:
        nxt[i] = nxt[nxt[i]]
    if s[i] == s[nxt[i] + 1]:
        nxt[i]++

这样复杂度看起来像是 $O(n^2)$ 的？其实不然，需要势能分析，我在这里尽量简单的说。

我们设势能为 $\Phi=\text{next}(i-1)$，那么每一次 while 循环的执行次数不会超过 $\Phi$。

这是显然的，因为跳 $\text{next}(i)$ 是一个严格递减的过程。

我们会发现，while 循环每执行一次，就会使得势能至少减 $1$，而外层每一轮 for 循环至多只会给势能增加 $1$。

因此 while 循环的总执行次数不会超过 $n$，所以这个算法是 $O(n)$ 的。

[模板] KMP

这是一个 KMP 算法的经典应用：字符串匹配。

我们的目标是在模板串 $S$ 中找到模式串 $T$ 的出现次数。

假设模板串当前匹配到 $i$，对应的模式串上一次匹配到 $j$（可能为 $0$），那么我们尝试把 $j$ 向下移动一个位置。

1. 如果成功，那么无事发生。

2. 如果失败，我们需要向右平移模式串 $T$，对应的 $j$ 应当减少。

   平移到什么程度为止呢？应当是第一次前缀恰好等于后缀的时候，其实就是 $\text{Border}$。

   如果失败就接着跳，一直到 $j=0$ 或者匹配上为止。

3. 特别地，如果把 $j$ 移动到了 $T$ 的末尾，我们需要尝试进行下一次匹配，令 $j\gets \text{next}(j)$ 即可。

复杂度同样是势能分析法，设势能为 $\text{next}(j)$，while 循环每执行一次至少会把势能减少 $1$，并且匹配成功后 $\Phi\gets \text{next}(j+1)$ 至多会把势能增加 $1$，因此执行次数不超过 $|S|$。

因此复杂度为 $O(|S|+|T|)$。

AC Code。

[模板] 失配树

每一个位置的 $\text{fail}$ 都严格小于它本身，所以我们可以认为这是一个树的结构。

两个位置的公共 $\text{Border}$ 等价于求它们的 LCA，但是注意，当它们的 LCA 是某个位置本身时，我们需要在跳一次失配，因为 $\text{Border}$ 不能是它本身。

此外，我们进行倍增 LCA 时，认为 $0$ 是不存在的节点会给我们一些方便，但是失配数组中 $0$ 代表没有 $\text{Border}$，所以我们需要把这些 $0$ 处理成一个别的数字，我这里使用了 $|S|+1$。

复杂度 $O(|S|\log |S| +m\log |S|)$。

AC Code。

[USACO03FALL] Milking Grid（数据加强版）

显然，我们需要对所有横向的字符串找到它们公共的周期，纵向也要找到公共周期。

由于周期唯一对应一个 $\text{Border}$，我们又知道 $\text{Border}$ 的数量是线性的，所以开一个桶计它们的出现次数即可取交集。

因此复杂度为 $O(RC)$。

AC Code。

[HNOI2008] GT考试

最终不含有不吉利数字，也就是 KMP 最终匹配到的位置是 $0\sim M-1$，所以设 $dp_{n,i}$ 表示在第 $n$ 步时匹配到了位置 $i$ 的方案数，考虑 $i$ 的下一步在哪里。

枚举下一个字符 $0\sim 9$，然后根据 KMP 的思路，求出下一步会匹配到的位置 $j$，并记录 $A_{j,i}$ 为 $i\to j$ 的次数。

我们可以写出转移方程：

$$dp_{n+1,j}=\sum_{i=0}^{M-1}A_{j,i}dp_{n,i}$$

这显然是一个矩阵的形式，矩阵快速幂即可。

进行匹配之前的位置仅有 $0$ 一种方案，所以 $dp_{0}=[1,0,\dots,0]^T$，那么求 $A^n\times dp_0$ 这个向量的和即可，复杂度是 $O(M^3\log N)$。

AC Code。

[NOI2014] 动物园

首先给出一个非正解：从失配树的角度考虑，首先一个位置的所有 $\text{Border}$ 是它在失配树的深度（$0$ 的深度为 $-1$），那么我们要找的就是深度 $\le \lfloor\frac{i}{2}\rfloor$ 的 祖先节点的数量，于是倍增跳父亲即可。

上面的做法是 $O(nL\log L)$ 的，如果实现不够好会被卡常

AC Code #1。

思考 KMP 构造失配数组的过程，当我们构建 $i$ 时，利用了 $i-1$ 的答案，那这个题目是否也能这样操作？

回顾 KMP 的基础，那就是，$S[1,i]$ 的 $\text{Border}$ 扣掉 $S_i$ 后一定是 $S[1,i-1]$ 的 $\text{Border}$。

同样地，$S[1,i]$ 的最长的 $\le \frac{i}{2}$ 的 $\text{Border}$ 扣掉 $S_i$ 后，一定是 $S[1,i-1]$ 的 $\le \frac{i}{2}-1$ 的 $\text{Border}$。

我们既然在前面的操作知道了 $S[1,i-1]$ 的最长的 $\le \frac{i-1}{2}$ 的 $\text{Border}$，设它是 $j$，那么 $i$ 的答案扣掉 $S_i$ 后一定在 $j$ 的 $\text{fail}$ 链上。

长度至多从 $\frac{i-1}{2}\to \frac{i+1}{2}$，处理这种情况只需要多跳一次 $\text{fail}$ 即可，复杂度 $O(nL)$。

AC Code #2。

[POI2005] SZA-Template

首先不难发现能成为印章的字符串是给定串 $S$ 的 $\text{Border}$，接下来我们考虑如何检查一个 $\text{Border}$ 能不能印完。

对于一个待检查的串 $T$，我们找到它在 $S$ 中所有的出现位置，它至多只能覆盖这些位置，并且不存在两个覆盖位置中间还能被覆盖的情况，因为如果这样的话中间那个位置也会被匹配上。

对于这些出现位置，在失配树上，它们的祖先中一定有 $T$ 对应节点，也就是说这些出现的位置都是 $T$ 的子孙。

现在的问题就变成了，我在一棵树上的一条指定链上走，使用某种数据结构维护子树的所有节点。

1. 如果是从上往下走，每次删除若干节点，并且在一条数轴上维护相邻距离的最大值。
2. 如果是从下往上走，每次添加若干节点，并且在一条数轴上维护相邻距离的最大值。

显然这个数据结构可以是线段树，但是如果从上往下走的话，每次操作去掉两个较小距离的贡献并且加上一个较大距离的贡献，我们只需要把最大距离对新贡献取最大值即可；如果从下往上走，每次操作去掉一个较大的贡献并加上两个较小的贡献，这个无法简单地取最大值。因此从上往下走的过程可以用链表维护这个数轴，复杂度做到 $O(|S|)$。

AC Code。