【学习笔记】border与period

其实只是抄抄博客啦

弱周期定理

$1.1$ 若$p$和$q$是$s$的周期，$p+q\le |s|$，则$\gcd (p,q)$也为$s$的周期

证明：
不妨设$p<q$，记$d=q-p$
由于$p+q\le |s|$，对于$\forall i\in [1,|s|-d],i-p\ge 1\vee i+q\le n$
若前者成立，$s_i=s_{i-p}=s_{i-p+q}=s_{i+d}$
若后者成立，$s_i=s_{i+q}=s_{i+q-p}=s_{i+d}$
故$d$为$s$的周期
显然最终可以得到$\gcd (p,q)$是$s$的周期

border的结构

$1.2$ 若$2|S|\ge |T|$，则$S$在$T$中的匹配位置必为等差数列。

证明：
先将$T$中没有被$S$覆盖的部分去掉
考虑匹配为大于$2$的情况
设$S$在$T$中第一二次的匹配位差为$d$，第二次与后面的某一次匹配位差为$q$，那么$d,q$均为$S$的周期，并且$d+q\le |S|$，根据弱周期定理$r=\gcd (d,q)$是$S$的周期，设$S$的最小周期为$p$，那么$p|r$（否则可以使用WPL构造更小的周期）。此时$p|r|d$。

若$p<d$，由于$p$是$S$的循环，因此可以找到一个距离第一匹配位更近的匹配位，与$d$的定义矛盾

因此只有可能$p=r=d$，并且$d|q$，所以匹配位在处理后的$T$上，每$d$出现一次，匹配位就是公差为$d$的等差数列了。

$1.3$ 字符串$s$所有不小于$\frac{|s|}{2}$的$\text{border}$构成一个等差数列

设$s$最大的$\text{border}$为$n-p(p\le \frac{|s|}{2})$,另一个$\text{border}$为$n-q(q\le \frac{|s|}{2})$
因为$p$,$q$是$s$的周期，所以$\gcd (p,q)$是$s$的周期
所以$n-\gcd (p,q)$是$s$的$\text{border}$
所以$p|q$
又因为$p$是$s$的周期，所以$s$的长相可以画出来
故$s$所有不小于$\frac{|s|}{2}$的$\text{border}$构成一个等差数列，公差为$p$

$1.4$ 推论：字符串$s$的所有$\text{border}$长度排序后可分成$O(\log |s|)$段，每段是一个等差数列

将$s$的$\text{border}$按长度$x$分成$\log |s|$类，记$2^k$为最大不超过$n$的$2$的次幂
$x\in [1,2),[2,4),...,[2^{k-1},2^k),[2^k,n)$
对于$x\in [2^k,n)$，显然$2^k\ge \frac{n}{2}$，那么该段构成一个等差数列
对于$x\in [2^{i-1},2^i)$，考虑一个巧妙的构造
直接放图吧应该看得懂233

两个公差为d1,d2的数列求交过后公差应该是lcm(d1,d2)吧

然后就可以切掉 Mivik 的标题 了。