后缀、Border的研究-学习笔记

· · 个人记录

by jcvb

性质

字符串 u, v 满足 2|u| ≥ |v|, 则 u 在 v 中的所有匹配位置组成一个等差数列。

字符串 s 的所有不小于 |s|/2 的 border 长度组成一个等差数列

证明: 设 s 的最大 border 长度为 n − p, (p ≤ |s|/2), 另外某个border 的长度为 n − q, (q ≤ |s|/2), 则 gcd(p, q) 是 s 的周期, 即n − gcd(p, q) 是 s 的 border 长度, 于是 gcd(p, q) ≥ p ⇒ p | q。

自己悟出来的：

如果串s的border> |s|/2，那么这个border的循环节也是大串的循环节。

应用

子串所有border（等差数列表示）

若 |u| = |v|, 记 PS(u, v) = {k : pre(u, k) = suf(v, k)}

记 LargePS(u, v) = {k ∈ PS(u, v) : k ≥ |u|/2}

我们按border的长度分类为[2^i,2^{i+1})，最后一段不足也没关系。

长度为2的整次幂的子串的出现位置（字典序排名）正好是后缀排序的过程！我们记录下来即可。

空间O(n\log n)，预处理O(n\log n)，每次询问O(\log^2n)，瓶颈在IPM的询问是O(\log n)的。

可以优化到每次询问O(\log n)：

## 子串最小border CF1043G $O(\sqrt{N})$找： 1.对于$\le \sqrt{N}$的border暴力找。 2.对于$>\sqrt{N}$的border： 那么$l$和$r-border+1$这两个后缀在后缀数组上的排名$\le \sqrt{N}

如果>，那么这个串的出现肯定会重叠，也就说明这个串有更小的border。

子串最大border

[BJWC2018]Border 的四种求法

子串最小后缀

法一：

设p=\arg\min_{i\in[l,r]}(s[i..n])

则答案为p的最小border

法二：

记f(l,r)为[l,r]的答案，则有

f(l,r)=\min(s[p..r],f(r-2^k+1,r))

其中2^k\le r-l+1<2^{k+1}

原因是有border的串的最小border一定\le len/2

于是可以预处理后O(1)查询。

子串最大后缀

求一个 p, 使得maxsuf(l, r) = max {s[p..r], maxsuf(r − m + 1, r)} 成立。

设 maxsuf(l, r) = s[x...r]。只需考虑 l ≤ x < r − m + 1 的情形,即需要求出 x。

证明：

为什么q|p_2-x？否则，串s[x..r]会有一个比q更小的周期w=\gcd(q,p_2-x)，那么p_2应该=p_1-w，否则，可以画图，然后根据s[r+1..n]<s[r+1-q..n]证明p_1-w更优。而且感性的理解也很奇怪，你说为啥p_2\neq p_1-w，而是一个奇奇怪怪的p_2=p_1-kw？

最后，显然真正的最长公共后缀一定是周期q不断往前延伸，否则反证法可以得到矛盾。