Border 理论小记

符号与约定

在本文中：

字符串索引默认从 $1$ 开始。

用 $s_{[l, r]}$ 表示子串 $s_l s_{l + 1} s_{l + 2} \ldots s_r$，特别地，当 $[l, r] = \varnothing$ 时表示空串。

用 $\mathrm{pre}(s, i)$ 表示 $s_{[1, i]}$，$\mathrm{suf}(s, i)$ 表示 $s_{[i, |s|]}$。

定义

对于一个字符串 $s$，若正整数 $i<|s|$ 满足 $\mathrm{pre}(s, i) = \mathrm{suf}(s, |s| - i + 1)$，则称 $\mathrm{pre}(s, i)$ 为 $s$ 的一个 Border。下文用 $\mathcal{B}(s)$ 表示 $s$ 的所有 Border 构成的集合。
对于一个字符串 $s$，若正整数 $k < |s|$ 满足 $\forall i \in (k, |s|], s_i = s_{i - k}$，则称 $k$ 为 $s$ 的一个周期（Period），特别地，若 $k \mid |s|$，则称 $k$ 为 $s$ 的一个整周期。下文用 $\mathcal{P}(s)$ 表示 $s$ 的所有 Period 构成的集合。

例如：对于字符串 $\texttt{abcab}$，$\texttt{ab}$ 是它的一个 Border，且它有一个 $3$ 的周期。

定理 1：对于一个字符串 $s$，若用 $t$ 表示其最长的 Border，则有 $\mathcal{B}(s) = \mathcal{B}(t) \cup \{t\}$。

也就是对于一个串，除了最长的 Border 以外，其他的 Border 都是最长 Border 的 Border。
证明就是考虑根据定义可以得到对于 $s$ 的任意一个除 $t$ 以外的 Border，都一定是 $t$ 的 Border。

稍微手玩一下就行，读者自证不难。

定理 2：一个字符串的 Border 与 Period 一一对应。具体地，$\mathrm{pre}(s, i) \in \mathcal{B}(s) \iff |s| - i \in \mathcal{P}(s)$。

证明考虑分讨 $i \le \frac{|s|}{2}$ 和 $i > \frac{|s|}{2}$ 两种情况即可。

前缀函数与 KMP 算法

根据性质 1，我们只需要知道一个串所有前缀的最长 Border，就可以求出该串的所有 Border。

对于一个字符串 $s$,我们定义其前缀数组为一个长度为 $|s|$ 的数组 $\pi$。其中 $\pi_i$ 为 $\mathrm{pre}(s,i)$ 最长 Border 的长度，特别地，若该前缀没有 Border，则 $\pi_i = 0$。

考虑在线地求出前缀函数，也就是根据 $\pi_1 \ldots \pi_{i - 1}$ 去求出 $\pi_i$。

首先容易发现，$\pi_i \le \pi_{i - 1} + 1$。更进一步地，当 $\pi_i > 1$ 时，我们有 $\mathrm{pre}(s, \pi_i - 1)\in\mathcal{B}(\mathrm{pre}(s, i - 1))$。根据这一点，我们得到了一个“朴素的暴力”：每次从 $\pi_{i - 1}$ 开始从大到小遍历 $\mathcal{B}(\mathrm{pre}(s, i - 1))$，记当前遍历到的长度为 $j$，若能向后扩展，即 $s_{j + 1} = s_i$，则有 $\pi_{i} = j + 1$。否则若遍历完所有 Border 还是找不到满足条件的 $j$，则 $\pi_i = [s_1 = s_i]$。

考虑分析这个算法的时间复杂度，用一个指针维护当前最后一个位置的 $\pi$，发现每次做下一个位置时指针最多增加 $1$，所以这个算法的时间复杂度是线性的。

参考代码：

// n is |s|.
for (int i = 2, j = 0; i <= n; i++) {
	while (j && s[j + 1] != s[i]) j = pi[j];
	if (s[j + 1] == s[i]) pi[i] = ++j;
}

单模式串字符串匹配

这是一个经典问题，即给定两个字符串 $s, t$，求 $t$ 在 $s$ 中所有出现的位置。其中出现是指 $t$ 与 $s$ 的一个子串相等，出现的位置就是这个子串的位置。

解决这个问题的朴素想法是枚举每个位置，然后将这个位置的子串与 $t$ 进行比较。

// n is |s|, m is |t|.
for (int i = 1; i + m - 1 <= n; i++) {
	int flag = 1;
	for (int j = 1; j <= m; j++)
		if (s[i + j - 1] != t[j]) {flag = 0; break;}
	if (flag) printf("%d ", i);
}
puts("");

考虑优化这个暴力，去除无用的枚举。

考虑设当前起点为 $i$，在 $s$ 的位置 $j + 1$ 失配时，我们想要找到一个最小的位置，使得其至少在 $j + 1$ 失配。
形式化地，我们需要求一个最大的 $l$，使得 $j - l + 1 > i, \mathrm{pre}(t, l) = s_{[j - l + 1, j]}$。

我们知道 $s_{[i, j]} = \mathrm{pre}(t, j - i + 1)$，因此等价于要求 $\mathrm{pre}(t, l) = t_{[j - i + 1 - l + 1, j - i + 1]}$，由此可得我们要求的 $l$ 实际上就是 $\mathrm{pre}(t, j - i + 1)$ 的最长 Border 的长度。

// n is |s|, m is |t|.
for (int i = 1, j = 0; i <= n; i++) {
	while (j && t[j + 1] != s[i]) j = pi[j];
	if (t[j + 1] == s[i])
		if (++j == m) {
			// ...
			j = nxt[j];
		}
}

容易发现 $j$ 每次至多增加 $1$，因此时间复杂度是 $O(n)$ 的。

其实还可以从另一个角度考虑这个问题，我们讲 $s$ 和 $t$ 拼起来得到 $t + \# + s$，其中 $\#$ 是一个不在 $t$ 和 $s$ 的字符集内的特殊字符，然后求它的前缀函数，发现匹配的位置就是在 $s$ 部分 $\pi = |t|$ 的位置。

因为 $\pi_i \le |t|$，所以实际上不需要记录 $s$ 部分的 $\pi_i$ 的具体值，因此只需要在 $t$ 上跑 KMP，然后用一个指针遍历 $s$，另一个指针维护当前的 $\pi_i$ 即可。写出来的码和上面是一样的。

失配树

考虑对于字符串的每个前缀建一个点，并对每个点 $i$ 向 $\pi_i$ 连一条边，可以发现这样得到了一棵内向树，我们称之为失配树。

对于每个前缀，其 Border 就是它在树上的所有非根祖先。

例题：CF1286E Fedya the Potter Strikes Back

给定一个字符串 $S$ 和一个序列 $W$，初始为空。

有 $n$ 次操作，每次操作在 $S$ 末尾添加一个字符并在 $W$ 末尾添加一个数。并询问：

$$\sum\limits_{S_{[L, R]} = S_{[1, R - L + 1]}} \min_{i = L}^R W_i$$

强制在线。

$1 \le n \le 6\times 10^5$。

TL: 4s, ML: 250MB.

只需考虑新串的所有 Border，再求前缀和即可。

容易发现新串的 Border 要么是原串的某个 Border 后面添加一个字符，要么长度为 $1$。也就是说每次只会新增至多一个 Border，只要能实现快速删除不合法的 Border 和更新答案这题就做完了。

考虑如何删除不合法的 Border，只需要对于每个前缀记录其第一个后继不同的祖先即可。

然后考虑更新答案，用一个 map 记录答案为某个值的区间的数量然后暴力推平，时间复杂度与颜色段均摊相同。

然后这题就做完了，时间复杂度为 $O(n\log n)$。

弱周期引理与周期引理

弱周期引理（Weak Periodicity Lemma）：

$$\forall p, q\in\mathcal{P}(s), p + q \le |s| \implies \gcd(p, q)\in\mathcal{P}(s)$$

证明：

令 $p < q$，设 $d = q-p$，只需证 $d \in \mathcal{P}(s)$，就可以用辗转相减法证明结论。

• $\forall i \in (d, |s| - p], s_i = s_{i + p} = s_{i + p - q} = s_{i - d}$
• $\forall i \in (q, |s|], s_i = s_{i - q} = s_{i - q + p} = s_{i - d}$

因为 $p + q \le |s|$，即 $q \le |s| - p$，因此 $(d, |s| - p] \cup (q, |s|] = (d, |s|]$。故 $d \in \mathcal{P}(s)$。

$\square$

一般情况下弱周期引理就够用了，但实际上有更紧的界。

在讲周期引理之前插入一个小定理：

定理 3：若字符串 $t$ 是字符串 $s$ 的前缀，且 $a \in \mathcal{P}(s), b \in \mathcal{P}(t), b \mid a, |t| \ge a$，且 $b$ 是 $t$ 的整周期，则有 $b \in \mathcal{P}(s)$。

容易发现 $a$ 是 $t$ 的周期，并且由于 $b \mid a$，就可以得到 $b$ 是 $s$ 的周期。
理解不了的可以尝试自己画个图。

周期引理（Periodicity Lemma）：

$$\forall p, q\in\mathcal{P}(s), p + q - \gcd(p, q) \le |s| \implies \gcd(p, q)\in\mathcal{P}(s)$$

证明：

令 $p < q$，设 $d = q - p$。

由于 $\forall i \in (d, |s| - p], s_i = s_{i + p} = s_{i + p - q} = s_{i - d}$，因此 $d \in \mathcal{P}(\mathrm{pre}(s, |s| - p))$。

考虑归纳，假设已经证明周期引理对于 $\mathrm{pre}(s, |s| - p)$ 成立。
因为 $p + q - \gcd(p, q) \le |s|$，两边同减 $p$ 得到 $p + (q - p) - \gcd(p, q - p) \le |s| - p$，因此 $\gcd(p, q) \in \mathcal{P}(\mathrm{pre}(s, |s| - p))$。

因为 $2p = p + q - (q - p) \le p + q - \gcd(p, q) \le |s|$，即 $p \le |s| - p$，因此有 $\gcd(p, q) \in \mathcal{P}(\mathrm{pre}(s, p))$。

由于 $\gcd(p, q) | p$，因此 $\gcd(p, q)$ 是 $s_{[1, p]}$ 的整周期，根据定理 3 即可得到 $\gcd(p, q) \in \mathcal{P}(s)$。

$\square$

其他定理

定理 4：对于文本串 $s$ 和模式串 $t$，若 $|t| \ge \frac{|s|}{2}$，且 $t$ 在 $s$ 中至少成功匹配了 $3$ 次，则每次匹配的位置形成一个等差数列，且公差为 $t$ 的最小周期。

证明：

考虑匹配成功的第 $1$ 次、第 $2$ 次和最后一次，分别记为 $t_1, t_2, t_x$。
设 $t_1, t_2$ 的间隔为 $d$，$t_2, t_x$ 的间隔为 $a$。显然 $d, a$ 都是 $t$ 的周期。

因为 $|t| \ge \frac{|s|}{2}$，所以 $t_1, t_x$ 的间隔不会超过 $|t|$。
所以 $d + a \le |t|$，根据弱周期引理，$\gcd(d, a)$ 也是 $t$ 的周期。

设 $t$ 的最小周期为 $p$，显然有 $p \le \gcd(d, a) \le d$，因此 $p + \gcd(d, a) \le d + \gcd(d, a) \le d + a \le |t|$，根据弱周期引理显然还有周期 $\gcd(p, d, a) \le p$。因为 $p$ 最小，故 $p\mid\gcd(p, d, a)$，因此 $p\mid d$。

若 $p\ne d$，则在与 $t_1$ 间隔 $p$ 的位置也会有一个匹配，因此一定有 $p = d$。

显然上面的分析中只要满足 $t_x$ 是第 $\ge 3$ 次匹配即可，因此相邻两次匹配的间隔一定都是 $p$ 的倍数，并且除最后一次外每次匹配间隔 $p$ 的位置一定也会有一个匹配。故所有匹配的间隔相同，即匹配的位置形成等差数列。

$\square$

然而我并没有在 OI 中见到什么题目需要用到这个定理，如果有人知道请告诉我，十分感谢！

upd on 2024/10/14: 现在有了，感谢学弟让我见到了这个题！

例题：CF1038F Wrap Around

给定一个字符串，字符集为 $\{0, 1\}$。求有多少长度为 $n$ 的字符串 $t$，满足以 $t$ 为循环节的无限循环字符串包含 $s$。

$1 \le |s| \le n \le 40$，但是我们把它加强到 $4000$。

TL: 2s, ML: 250MB.

加强到 $4000$ 做法还是挺多的，这里讲一个我的用到上面这个定理的做法。

考虑 $s$ 出现的位置，如果在 $t$ 中出现了，那可以设 $dp_{i, j}$ 表示考虑前 $i$ 个字符，$s$ 匹配到 $j$ 的方案数，然后用 KMP 自动机转移一下，在 $j = |s|$ 时统计答案即可。

然后考虑所有 $s$ 都经过头尾的方案，假设已经知道所有 $s$ 覆盖的长度，剩余部分的方案数即为这样一个问题：求有多少长度为 $len$ 的字符串 $t$，满足 $s + t + s$ 只在头尾能匹配到 $s$。

做法和上面的 DP 类似，将初值设为 $dp_{0, \pi_{|s|}} = 1$，然后对于每个 $i$，设答案为 $sum_i$，则有：

$$sum_i = \sum\limits_{j \notin \mathcal{P}} dp_{i, j}$$

然后考虑 $s$ 的方法，分类讨论：

• 如果只放了 $1$ 个，则起点可以选在 $s_2$ 到 $s_{|s|}$，答案为 $(|s| - 1) sum_{n - |s|}$。
• 如果放了 $\ge 3$ 个，根据定理 4，相邻两个的位置差为最小周期，设为 $p$，则放了 $i$ 个的答案为 $(|s| - (i - 1)p - 1) sum_{n - (|s| - (i - 1)p)}$。注意需要满足所有的 $s$ 有交，即 $(i - 1)p < |s|$。
• 如果放了 $2$ 个，则枚举 Border 作为交，每次需要 check 中间能不能再匹配别的 $s$，设交的长度为 $i$，则答案为 $(i - 1) sum_{n - (2|s| - i)}$。

注意需要保证 $s$ 覆盖的长度 $\le n$。

但是这样仍是有问题的，考虑 $n = 5, s = \verb|101|$，发现当放了 $2$ 个时第一个串和第二个串头尾重叠了，这是我们没有统计到的。因此对于放了 $\ge 2$ 个的情况，需要判断一下第一次 $\ge n$ 时能否叠在一起，如果可以则也要计入答案。

定理 5：一个字符串 $s$ 的所有长度不小于 $\frac{|s|}{2}$ 的 Border 的长度构成一个等差数列。

证明：

设最长的 Border 的长度为 $|s| - p$，另一个 Border 的长度为 $|s| - q$，且有 $p, q \le \frac{|s|}{2}$。

由弱周期引理可知 $\gcd(p, q)$ 也是 $s$ 的周期，故 $p \le \gcd(p, q)$，因此 $p \mid q$。

容易发现每次将最长的 Border 删去最后 $p$ 个字符都会得到一个新的 Border，所以所有长度不小于 $\frac{|s|}{2}$ 的 Border 构成了一个等差数列。

$\square$

定理 6：一个字符串的所有 Border 的长度排序后可以划分成 $\lceil\log_2|s|\rceil$ 个连续段，使得每段都是一个等差数列。

首先可以将定理 5 扩展一下，把 $|s|$ 也加进去，依然构成等差数列。

这样每次取出长度大于 $\frac{|s|}{2}$ 的 Border，然后以剩下的最长 Border 作为 $s$，递归划分即可。

$\square$

基于定理 5 和定理 6，可以大大优化寻找 Border 和处理 Border 的复杂度。

例题：WC2016 论战捆竹竿

给定长度为 $n$ 的字符串 $s$，维护一个字符串 $t$，初始为空，每次选则一个非负整数 $a$ 使得 $\mathrm{suf}(t, |t| - a + 1) = \mathrm{pre}(s, a)$，令 $t \gets t + \mathrm{suf}(s, a + 1)$，问在 $|t| \le w$ 的情况下 $|t|$ 有多少种取值。

多组数据，$T\le 5, n\le 5\times 10^5, w\le 10^{18}$。

TL: 1s, ML: 120MB.

显然除了第一次外 $a$ 可以是 $s$ 的任意 Border 的长度，因此问题转化为求 $\sum a_i x_i$ 在区间 $[0, w - |s|]$ 中有多少种取值，其中 $a_i$ 为 $s$ 的周期。

然后考虑同余最短路，朴素做法是 $O(\min\mathcal{P}(s) \times |\mathcal{P}(s)|) = O(|s|^2)$ 的。

考虑对每个等差数列分开来处理。对于一个等差数列 $x, x + d, \ldots, x + kd$，在 ${}\bmod x$ 意义下跑同余最短路，那就相当于每次可以 $+0, +d, +2d, \ldots, +kd$。容易发现可以划分成 $\gcd(x, d)$ 个环，并且每个环互不影响，那就对每个环分开来做。然后对于一个环，能转移过来的就是一段区间，显然最小值不会被更新，因此从最小值开始断开变成链然后用单调队列维护就好了。

然后剩下来的问题就是合并，也就是要求模数改变后的结果。

设在模 $pre$ 意义下的结果为 $f$，模 $now$ 意义下的结果为 $g$，显然有 $g_i = \min_{f_j \equiv i \pmod{now}} f_j$。

然后由于 $f_i$ 的意义是 $f_i + k\times pre$ 都能被走到，因此在 $g$ 上 $g_i$ 可以更新到 $g_{i + k\times pre}$，因此需要再像上面一样跑一遍 DP。

时间复杂度为 $O(Tn\log n)$。

回文 Border

定理 7：回文串的回文前/后缀即为该串的 Border。

一般是根据这个性质可以把回文前缀转化成 Border 然后用定理 5 和定理 6优化。

定理 8：若回文串 $s$ 有周期 $p$，则可以把 $\mathrm{pre}(s, p)$ 划分成长度为 $|s| \bmod p$ 的前缀和长度为 $p - |s| \bmod p$ 的后缀，使得它们都是回文串。

画下图就明白了：

语言描述的严谨证明：

用 $\mathrm{rev}(s)$ 表示将 $s$ 翻转后得到的串，则：$\mathrm{pre}(s, |s|\bmod p) = \mathrm{rev}(\mathrm{suf}(s, |s| - |s| \bmod p + 1))$。并且显然有 $\mathrm{pre}(s, |s|\bmod p) = \mathrm{suf}(s, |s| - |s| \bmod p + 1)$，因此 $\mathrm{pre}(s, |s|\bmod p)$ 是回文串。

考虑字符串 $s_{(|s|\bmod p, s - |s|\bmod p]}$，若其长度超过 $p$，显然 $p$ 也是它的周期，同样方法可以证明 $s_{(|s|\bmod p, p]}$ 是回文串。否则，显然为 $s_{(|s|\bmod p, p]}$ 且是回文串。

$\square$

定理 9：若 $t$ 是回文串 $s$ 的最长 Border 且 $|t| \ge \frac{|s|}{2}$，则 $t$ 在 $s$ 中只能匹配 $2$ 次。

证明考虑反证，如果超过 $2$ 次则可以推出更长的 Border。

这两个定理也没有找到什么应用……

Significant Suffixes

记 $\mathrm{Ssuf}(s)$ 为在 $s$ 后接任意一个串后可能成为最小后缀的串的集合。形式化地，$t\in \mathrm{Ssuf}(s) \iff$ 存在一个字符串 $u$（可以为空）使得 $t + u$ 是 $s + u$ 的最小后缀。

定理 10：对于任意一个字符串以及 $u, v\in\mathrm{Ssuf}(s), |u| < |v|$，一定有 $u$ 是 $v$ 的 Border。

显然。

定理 11：对于任意一个字符串 $s$ 以及 $u, v\in\mathrm{Ssuf}(s), |u| < |v|$，一定有 $2|u| \le |v|$。

证明：

由定理 10 可得 $u$ 是 $v$ 的一个 Border。

假设 $2|u| > |v|$，设与 $u$ 对应的周期为 $p$，记 $t = \mathrm{pre}(v, p)$，则 $u, v$ 可以表示为 $u = t + w, v = t + t + w$。

若存在一个字符串 $r$ 使得 $u + r < v + r$，则 $t + w + r < t + t + w + r$，即 $w + r < t + w + r$，即 $w + r < u + r$，因此永远无法找到一个字符串 $r$ 使得 $u + r < w + r$ 且 $u + r < v + r$，因此 $u \notin \mathrm{Ssuf}(s)$，矛盾。

$\square$

定理 12：$|\mathrm{Ssuf}(s)| \le \log_2|s|$。

由定理 11 可得。

例题：ZJOI2017 字符串

维护一个动态字符串 $s_{1..n}$，字符串的字符集是所有 $|x| \le 10^9$ 的整数。要求支持两个操作：

1. 输入 $l, r, d$，对于所有 $l \le i \le r$，将 $s_i$ 修改为 $s_i + d$，注意 $d$ 可能是负数。
2. 输入 $l, r$，输出子串 $s_{l..r}$ 的字典序最小的后缀的起点位置。即，如果最小后缀是 $s_{p..r}$（$l \le p \le r$），请输出 $p$。

$1 \le n \le 2\times 10^5, 1 \le q \le 3\times 10^4, |s_i| \le 10^8, |d| \le 10^3$。

TL: 3s, ML: 500MB.

用线段树维护，在线段树每个节点上维护这个区间的 $\mathrm{Ssuf}$，合并左右儿子时，由于左右儿子长度几乎相等，因此左儿子只会保留一个。取出左儿子的所有 $\mathrm{Ssuf}$ 进行比较，如果能比较出大小（指其中一个不是另一个的前缀）则扔掉大的那个，否则扔掉短的。

这样已经可以保证每个节点是 $O(\log n)$ 个了，但并不是真正的 $\mathrm{Ssuf}$，要把右儿子的集合也取出来与左儿子保留的那个进行比较，如果比出大小则扔掉大的那个。这样可以有效减小常数。

对于查询，由于只会找到线段树上 $O(\log n)$ 个区间，可以把所有 $O(\log^2 n)$ 个后缀都取出来进行比较。

后缀大小比较需要二分加哈希，由于有修改操作，哈希值也许要数据结构维护。如果用线段树，则复杂度为 $O(n\log^3 n + m\log^4 n)$，用 $O(\sqrt{n})$ 修改 $O(1)$ 查询的分块维护就可以变成 $O(n\log^2 n + m\log^3 n + m\sqrt{n})$，可以通过。

参考资料

• 前缀函数与 KMP 算法 - OI Wiki
• Border理论小记 - 洛谷专栏
• 如何更好地理解和掌握 KMP 算法? - 知乎
• Periodicity Lemma - 知乎