border 的一些性质

有时候一些神仙字符串题会用到 border 的性质来转化或者证明复杂度，记一下这些有用的结论。

记号：

1. 字符串：\(s_{1, ..., n}\)，长度为 \(|s|\)

2. 子串：\(s_{[l, r]}\)

3. 前 / 后缀：\(pre(s, i), suf(s, i)\) 分别表示字符串 \(s\) 长度为 \(i\) 的前 / 后缀。

4. 最小周期：\(pre(s)\) 表示字符串 \(s\) 的最小周期。

令：

1. \(P(u, v) = \{ k \mid pre(u, k) = suf(v, k) \}\)

2. \(LP(u, v) = \{ k \in P(u, v), k \geq \frac{|u|}{2}\)

定义：

周期：\(\forall 0 \leq p < |s|\)，如果 \(\forall 1 \leq i \leq |s| - p\) 有 \(s_i = s_{i + p}\)，则称 \(p\) 是字符串 \(s\) 的一个周期。

border：若 \(\forall 0 \leq r < |s|\)，有 \(pre(s, r) = suf(s, r)\)，则称 \(pre(s, r)\) 是 \(s\) 的一个 border.

注意有时 border 的定义是 \(pre(s, r)\) 的长度。

border 和周期：

1. \(pre(s, k)\) 是 \(s\) 的 border \(\Leftrightarrow\) \(|s| - k\) 是 \(s\) 的周期。

2. 若 \(p, q\) 都是 \(s\) 的周期，且 \(p + q \leq |s|\)，则 \(\gcd(p, q)\) 也是 \(s\) 的周期。

3. 若 \(p, q\) 都是 \(s\) 的周期，且 \(p + q - \gcd(p, q) \leq |s|\)，则 \(\gcd(p, q)\) 也是 \(s\) 的周期。

字符串匹配：

1. 若字符串 \(u, v\) 满足 \(2 |u| \geq |v|\)，则 \(u\) 在 \(v\) 中匹配的位置是一个公差为 \(per(u)\) 的等差数列。此时 \(v\) 是 \(u\) 最小周期的重复。

border 的结构：

1. 字符串 \(s\) 的所有不短于 \(\frac{|s|}{2}\) 的 border 长度构成等差数列。
   等价：本质不同的短于 \(\frac{|s|}{2}\) 的 border 只有一个。

2. 将 \(s\) 的 border 按长度划分成 \([2^i, 2^{i + 1} - 1), ..., [2^k, |s|)\) 等集合，则一个 border 集合可以表示成 \(LP(pre(s, 2^i), suf(s, 2^i))\)

3. \(LP(u, v)\) 构成一个等差数列。

4. 推论：\(s\) 的所有 border 排序后可以划分成 \(O(\log |s|)\) 段，每段是一个等差数列。

这个可以推出 P4482 [BJWC2018]Border 的四种求法 的 \(O(n \log n)\) 做法，非常强大。