border与period学习笔记

起因是觉得自己对border这一套理论完全不会，来学一手

符号定义

以下默认 $s$ 为一个字符串

$s[i]$ 表示字符串 $s$ 下标为 $i$ 的字符

$s[i,j]$ 表示字符串 $s$ 下标位于 $[i,j]$ 的子串

$pre(s,x)$ 表示字符串 $s$ 长度为 $x$ 的前缀

$suf(s,x)$ 表示字符串 $s$ 长度为 $x$ 的后缀

定义

若 $0\leq r<|s|,pre(s,r)=suf(s,r)$ ，则称 $r$ 为 $s$ 的一个 $\text{border}$

若 $0<p\leq |s|,s[i]=s[i+p],\forall i\in[1,|s|-p]$ ，则称 $p$ 为 $s$ 的一个 $\text{period}$ （周期）

记最小周期为 $per(s)$

显然， $r$ 为 $\text{border}$ $\iff$ $|s|-r$ 为 $\text{period}$

引理

$\text{Weak Periodicity Lemma}$

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

证明：

不妨设 $p<q$ ，记 $d=q-p$

由于 $p+q\leq |s|$ ，对于 $\forall i\in[1,|s|-d]$ ， $i-p\geq 1\or i+q\leq |s|$ 一定成立

若前者成立， $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$ 的周期

$\text{Periodicity Lemma}$

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

字符串匹配

众所周知，字符串匹配问题由KMP算法解决

引理：若字符串 $s,t$ 满足 $|s|\geq \dfrac{|v|}{2}$ ，则 $s$ 在 $t$ 中所有匹配位置构成一个等差数列，公差为 $per(s)$

证明：

我们仅考虑匹配次数大于2的情况，否则显然为等差数列

由于 $2|s|\geq |v|$ ，所以任意两次匹配间必有交点，任意两次匹配位置之差为 $s$ 的一个 $\text{period}$

考虑取出第一二次匹配 $u_1,u_2$ ，与某次匹配 $u_x$

记 $u_1$ 与 $u_2$ 匹配位置之差为 $d$ ， $u_2$ 与 $u_x$ 的位置差为 $q$

易得 $d,q$ 为 $s$ 的 $\text{period}$ ，由 $\text{Weak Periodicity Lemma}$ ，可知 $g=\gcd(d,q)$ 也为一个周期

设 $s$ 的最小周期 $p\leq g\leq q\leq |u_1\cap u_2|$ ，故 $p$ 为 $u_1\cap u_2$ 的周期，可得 $p$ 为 $u_1\cup u_2$ 的周期

若 $p<d$ 则 $u_2$ 左移 $p$ 产生匹配，故 $p\geq d$ ，又 $p\leq g=\gcd(d,q)\leq d$ ，所以 $p=d$

则 $d|q$ ，故结论成立，公差为 $per(s)$ （含3次匹配以上）

$\text{border}$ 的结构

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

证明：

记 $s$ 最大的 $\text{border}$ 为 $n-p,(p\leq \dfrac{|s|}{2})$ ，另外某个 $\text{border}$ 为 $n-q,(q\leq \dfrac{|s|}{2})$

由于 $p,q$ 为 $\text{period}$ ，由于 $\text{Weak Periodicity Lemma}$ 引理， $\gcd(p,q)$ 为 $\text{period}$

则 $n-\gcd(p,q)$ 为 $s$ 的一个 $\text{border}$ ，又 $\gcd(p,q)\leq p$ ，且 $n-p$ 为最大的 $\text{border}$

故 $\gcd(p,q)=p$ ，所以 $p|q$

故字符串 $s$ 所有不小于 $\dfrac{|s|}{2}$ 的 $\text{border}$ 构成一个等差数列，公差为 $p$ （最小 $\text{period}$ ）

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

将 $s$ 的 $\text{border}$ 按长度 $x$ 分成 $\log|s|$ 类，记 $2^k$ 为最大不超过 $n$ 的 $2$ 的次幂

$x\in[1,2),[2,4),\dots,[2^{k-1},2^k),[2^k,n)$

对于 $x\in[2^k,n)$ ，显然 $2^k\geq\dfrac{n}{2}$ ，根据引理该段构成一个等差数列

对于 $x\in[2^{i-1},2^i)$ ，考虑证明其也是一个等差数列

对于长度相等的两个字符串 $u,v$ ，记 $PS(u,v)=\{k|pre(u,k)=suf(v,k)\}$

记 $LargePS(u,v)=\{k\in PS(u,v)|k\geq\dfrac{|u|}{2}\}$

那么 $x\in[2^{i-1},2^i)$ 的 $\text{border}$ 集合为 $LargePS(pre(s,2^i),suf(s,2^i))$

类似引理的证明，容易得到 $LargePS(u,v)$ 构成一个等差数列

故结论得证

子串周期查询

给定字符串 $s[1,n]$ ，每次询问子串 $t=s[l,r]$ 的所有周期，用 $O(\log n)$ 个等差数列表示

求出所有 $\text{border}$ 即可

按 $\text{border}$ 的结构划分

$\text{border}$ $x\in[2^{i-1},2^i)$

若 $u\in LargePS(pre(t,2^i),suf(t,2^i))$ ，则 $pre(t,2^{i-1})$ 为其前缀， $suf(t,2^{i-1})$ 为其后缀

我们仅需求出 $pre(t,2^{i-1})$ 在 $suf(t,2^i)$ 中匹配的开头位置集合与 $suf(t,2^{i-1})$ 在 $pre(t,2^i)$ 中匹配的结尾位置集合翻转后取交

由于前面字符串匹配的结论，我们所求的匹配位置成一个等差数列

考虑仅需求出第一二次和最后一次的匹配位置，我们就能算出等差数列的首项、公差和末项

实现 $succ(v,i),pred(v,i)$ 表示 $v$ 从 $i$ 开始向前后的第一次匹配位置即可

由于 $v$ 的长度为 $2$ 的次幂，考虑同后缀数组一半倍增，每次将数组记录下来，空间 $O(n\log n)$

用 $succ/pred$ 时二分即可得

值得一提的是，上面求 $succ/pred$ 的算法被称为 $\text{Internal Pattern Matching}$

如何对等差数列取交？

存在引理证明若所求两个等差数列长度都不少于3，则他们的公差相等，容易 $O(1)$ 求交

否则枚举小长度即可，复杂度 $O(1)$
$\text{border}$ $x\in[2^k,|t|)$

考虑将情况1的 $2^i$ 改为 $|t|$ ，仍然成立

目前为止，我们已经得到了时间 $O(n\log n)-O(\log^2 n)$ ，空间 $O(n\log n)$ 的做法

$O(n\log n)-O(\log^2 n)$ 的做法暂时不大会（

[BJWC2018]Border 的四种求法