题解 P4482 【[BJWC2018]Border 的四种求法】
_sys
·
·
题解
子串周期查询
本文介绍了字符串结构相关的若干性质与能够在 O(n\log n) 预处理，O(\log n) 询问子串所有周期的算法。
后文会证明子串的所有周期能够通过特殊的形式表示，所以输出不会成为瓶颈。
符号定义。
字符串：s_{1\ldots n}。串长为 |s|。
子串：s_{[l,r]}。
前缀 pre(s, i) = s_{1, i}。后缀 suf(s, i)=s_{[|s|-i+1,|s|]}。
周期和 \text{border}。
若 0< p \leq |s|，对于 1\leq i\leq |s| - p 有 s_i=s_{i+p}，就称 p 为 s 的一个周期，最小周期写作 per(u)。
若 0\leq r < |s|，pre(s, r) = suf(s, r)，就称 pre(s, r) 是 s 的 \text{border}。
本文所述 \text{border} 定义与原题有差别。
一个显然的结论：s_{1..k} 为 s 的 \text{border}\rightleftharpoons|s| - k 为 s 的周期。
证明：令 $d=q-p\ (q > p)$， $i - p < 0$ 和 $i + q \leq |s|$ 至少有一个成立，于是要么得到 $s_i=s_{i-p}=s_{i-p+q}=s_d$ 要么得到 $s_i=s_{i+q}=s_{i+q-p}=s_d$。
于是 $d$ 和 $p$ 都是 $s$ 的周期，$d+p\leq |s|$，发现这是一个更相减损的过程，最后便会得到 $\gcd(p, q)$ 也为 $s$ 的周期。
$\textbf{Periodicity Lemma}$：若 $p$ 和 $q$ 是 $s$ 的周期，$p+q-\gcd(p, q)\leq |s|$，则 $\gcd(p, q)$ 也是 $s$ 的周期。
***
#### 字符串匹配
熟知的字符串匹配算法有 $\text{KMP}$。
其中 $fail_i$ 表示了 $s_{1,i}$ 的最长 $\text{border}$。
而很显然地 $\text{border}$ 的 $\text{border}$ 是 $\text{border}$。
所以一个字符串的所有 $\text{border}$ 便为 $fail_{|s|},fail_{fail_{|s|}},fail_{fail_{fail_{|s|}}},\ldots$。
**引理**：字符串 $u$ 和 $v$ 满足 $2|u| \geq |v|$，则 $u$ 在 $v$ 中的所有匹配位置组成一个等差数列，公差为 $per(u)$。
证明：只考虑匹配次数大于 $2$ 的情况。$2|u|\geq|v|$ 表明了两次匹配之间 $u$ 的位置必有交，而两次位置之差必定为 $u$ 的一个周期。
考虑第一次第二次和最后一次匹配，根据 $\textbf{Weak Periodicity Lemma}$ 可知 $\gcd$(第一次和第二次距离之差，第二次和最后一次距离之差) 为 $u$ 的周期。
通过简单的反证法可以得出它便是 $u$ 的最小周期。从而得到 $v$ 在此的结构为 $u$ 的最小周期的不断重复。
***
#### $\text{border}$ 的结构
**引理**：字符串 $s$ 的所有不小于 $\frac{|s|}2$ 的 $\text{border}$ 长度组成一个等差数列。
证明：有等价的说法为本质不同的长度小于 $\frac{|s|}2$ 的 $s$ 的周期至多只有一个。用简单的反证法与 $\textbf{Weak Periodicity Lemma}$ 可以得到。
现在我们将 $\text{border}$ 按照长度分类，分为 $[1, 2), [2, 4), [4, 8), \ldots [2^{k-1}, 2^k), [2^k, |s|)$ 这些集合。
对于长度相同的两个字符串 $u, v$，记 $PS(u, v)=\{k|pre(u, k)=suf(v, k)\}$。
记 $LargePS(u, v)=\{k\in PS(u, v)|k \geq \frac{|u|}2\}$。
则一个 $\text{border}$ 集合可以表示为 。$LargePS(pre(s, 2^i), suf(s, 2^i))$。
**引理**：$LargePS(u, v)$ 组成一个等差数列。
证明：$\text{border}$ 的 $\text{border}$ 是 $\text{border}$。对于这个集合里最长的 $\text{border}$ 而言，不小于它长度一半的 $\text{border}$ 长度组成一个等差数列。
**推论**：字符串 $s$ 的所有 $\text{border}$ 长度排序后可分成 $O(\log |s|)$ 段，每段是一个等差数列。
有了这个推论，可以尝试 [[WC2016]论战捆竹竿](https://www.luogu.com.cn/problem/P4156)。
***
#### 子串周期查询
* 给定字符串 $str$，每次询问 $str$ 一个子串的所有周期，用 $O(\log |str|)$ 个等差数列表示。
为方便起见，我们总是先求 $\text{border}$ 再推出周期。
我们设给定的子串为 $s$。
先考虑长度为 $[2^{i-1}, 2^i)$ 的集合。
假设 $\text{border}$ 为 $s_{1\ldots k}$，称他为 $t$。它合法当且仅当 $pre(t, 2^{i-1})=pre(s, 2^{i-1}), suf(t, 2^{i-1})=suf(s, 2^{i-1})$。
于是我们可以求出 $pre(s, 2^{i-1})$ 在 $pre(s, 2^i)$ 中的匹配位置与 $suf(s, 2^{i-1})$ 在 $suf(s, 2^i)$ 中的匹配位置的交集（移位后）。
而匹配位置为一个等差数列。我们只用求第一次匹配第二次匹配与最后一次匹配便可知道这个等差数列的首项、公差、项数。相当于实现一个 $succ(v, i)$ 和 $pred(v, i)$ 表示求 $v$ 从位置 $i$ 开始向前/后的第一次匹配位置。
问题变为 $str$ 中所有长度为 $2^{i-1}$ 的串有哪些位置能够与之匹配。
发现这就是倍增求后缀数组的时候把每一轮结束后的结果都记录下来。
最后是长度为 $[2^k, |s|)$ 的集合。做法其实一样，把上面所有 $2^i$ 替换为 $|s|$ 即可。
于是我们就有了 $O(n\log n)$ 预处理，单次询问 $O(log^2n)$ 的优秀做法。
如何优化？考虑将 $O(log^2n)$ 降低。这时瓶颈为求出等差数列、等差数列求交。
等差数列求交的优化肯定建立在字符串性质上。
**引理**：四个字符串满足 $|x_1|=|y_1|\geq|x_2|=|y_2|$，且 $x_1$ 在 $y_2y_1$ 中至少匹配 $3$ 次，$y_1$ 在 $x_1x_2$ 中至少匹配 $3$ 次，则 $x_1$ 和 $y_1$ 的最小周期相等。
证明：否则不妨设 $per(x_1) > per(y_1)$，考虑 $x_1$ 在 $y_2y_1$ 中的最右边一次匹配, 设它与 $y_1$ 的重叠部分为 $z$。
则 $|z| \geq 2per(x_1) > per(x_1) + per(y_1)$, 则 $z$ 拥有周期 $d = \gcd (per(x_1), per(y_1))|per(x_1)$, 于是 $d$ 也是 $x_1$ 的周期。但 $d < per(x_1)$, 矛盾。
同样，$y_1$ 在 $x_1x_2$ 里至少匹配 $3$ 次保证了 $per(x_1)<per(y_1)$ 矛盾。
所以我们合并的两个等差数列要么长度不足 $3$，要么公差相同。所以可以 $O(1)$ 合并。
求出等差数列的优化如下。
注意到在求 $succ(v, i)$ 的时候，$|v|$ 是二的幂，我们只在意起点在 $[i, i+|v|]$ 的匹配。
我们把原串按 $2^k$ 为段长分成若干段，考虑长度为 $2^k$ 的串的匹配信息。这样 $[i, i + |v|]$ 的匹配最多跨越两个段。我们可以分别得到这两个段的信息，直接合并即可。
如何维护匹配信息呢？我们发现最多只有 $O(n)$ 个长度为 $2^k$ 的串在原串中匹配了至少一次。而 $k$ 的取值有 $O(\log n)$ 种。所以匹配信息的空间是 $O(n\log n)$ 的。我们可以用 $\text{hashtable}$ 来解决。设 $h_{i,k}$ 表示 $S_{[i, i + 2^k]}$ 的哈希值，发现 $h_{[i, k]}$ 可以由 $h_{[i, k - 1]}$ 和 $h_{[i+2^{k-1}, k-1]}$ 在 $O(1)$ 的时间求出。所以预处理时间为 $O(n\log n)$。
这样就可以做到 $O(1)$ 求出等差数列。
至此，我们完成了所有的工作！
时间复杂度：$O(n\log n)-O(\log n)$。
空间复杂度：$O(n\log n)$。