Border Theory

· · 个人记录

其实是填坑。

记一个字符串 s 长为 p 的前缀为 \operatorname{pre}(s,p)，长为 q 的后缀为 \operatorname{suf}(s,q)。字符串 s 的长度记为 |s|，那么 s 可由 |s| 个字符拼接表示，第 i 字符为 s_i。

周期与 Border

如果 1 \leq p < |s|，且 \forall i,s_i=s_{i+p}，称 p 为 s 的周期。per(s) 表示 s 的最小周期。

如果 1 \leq q < |s|，且 \operatorname{pre}(s,q)=\operatorname{suf}(s,q)，称 q 为 s 的 Border。

显然一个字符串 s 的一个 Border p 会对应一个周期 |s|-p。

Weak Periodicity Lemma

如果字符串 s 有周期 p,q，满足 p+q\leq |s|，则 \gcd(p,q) 也为 s 的周期。

根据周期定义，假设 p<q，不难发现 q-p 为周期。类似于更相减损，可得到 \gcd(p,q) 为周期。

想去掉 Weak 的话把限制缩成 p+q+\gcd(p,q) \leq |s| 就好了。虽然实际应用一般。

推一个引理：如果字符串 u,v 满足 2|u| \geq |v|，则 u 在 v 里匹配位置构成一个等差数列；如果项数不小于 3，那么公差为 per(u)。

证明的话，考虑第一次，第二次以及最后一次匹配。记第一次和第二次匹配位置之差为 d，第二次和最后一次匹配位置之差为 q。显然 d,q 都是 u 的周期；若 u 存在比 \gcd(d,q) 更小的周期，那么 d 显然会变得更小，矛盾。所以 per(u) = d \leq p \leq \gcd(d,q)，证毕。

Border Theory

几乎是把 Border 与周期联系证明的，具体证明不难，根据上面的内容摆结论就好了。

  1. 对于一个字符串 s，其长度大于等于 \frac{|S|}{2} 的 Border 构成一个等差数列（运用：失配树 10MiB 版，HNOI2019 JOJO）；
  2. 对于两个字符串 u,v，记 \operatorname{LargePS}(u,v) = \{k:\operatorname{pre}(u,k)= \operatorname{suf}(v,k),k \geq \frac{|u|}{2}\}，则 \operatorname{LargePS}(u,v) 的元素构成一个等差数列；
  3. 一个字符串的所有 Border 可以划分成 O(\log n) 个等差数列（运用：Mivik 的标题，论战捆竹竿）。

没了。