Border Theory

· · 个人记录

引一个同学对字符串的评价：“很难想象字符串算法到底是在怎样的精神状态下搞出来的” 很难不支持（

感觉字符串很多东西都很反直觉 很神秘很有性质 这里对于一些不太显然的结论进行一个总结

\color{blue}\text{定理 1}

一个串的 border 与周期一一对应

个人认为这个和 \color{blue}\text{定理 2} 是最重要的结论 后面的证明用这两个很方便

对应方式在证明里

一个border对应唯一的周期：蓝色箭头相等因为 T 是 S 的 border 紫色箭头相等是因为这是 S 的相同位置 红框为 border T 对应的周期

下图是当 |T|\ge \dfrac{|S|}{2} 时的对应

是单射因为这样对应周期长度与 border 长度单射

下图是当 |T|< \dfrac{|S|}{2} 时的对应 更加简单

现在有了border到周期的单射了

下面考虑周期到 border

扔掉从头开始的完整的周期就直接可以完成单射

所以一一映射了 所以一一对应

这个结论非常有用 因为 border 太抽象了 分析问题的时候通过周期去考虑问题更直观

一个字符串 $S$，若其有 $p$ 和 $q$ 长度的周期，且 $p+q\le|S|$，则 $s$ 有长度为 $\gcd(p,q)$ 的周期 $\gcd$ 这个结论大概比较直观 但是 $p+q\le |S|$ 的限制更重要 当然这只是弱化版结论 但一般弱化版结论就够用了 强化版限制是 $p+q\le|S|+\gcd(p,q)

不妨设 p<q

我们首先证明 若其有 p 和 q 长度的周期，且 p+q\le|S|，则 s 有长度为 d=q-p 的周期

考虑蓝色大括号的部分 有 i> q 所以存在字符串的一个位置 s_{i-q} 因为有长度为 q 的周期 所以 s_{i-q}=s_i 又因为有长为 p 的周期 所以 s_i=s_{i-q}=s_{i-q+p}=s_{i-d} 所以对于 s[q-d+1,n] 这一子串 有 d 的周期

同理 我们考虑红色大括号的部分 有 i\le n-p 所以存在一个位置 s_{i+p} 和上面基本上一样的证明方式 所以对于 i>d 有 s_{i}=s_{i+p}=s_{i-q+p}=s_{i-d} 所以对于 s[1,n-p] 这一子串 有 d 的周期

所以我们现在的结论是 s[q-d+1,n] 和 s[1,n-p] 都有 d 的周期 需要这两部分覆盖整个串 即 q-d+1\le n-p+1 即 p+q\le n+d

哦 好像这样直接强化版结论也给证了（

我们先证弱化版 这样显然 p+q\le n 的时候上面的式子一定成立

故证毕若 S 有 p 和 q 长度的周期，且 p+q\le|S|，则 s 有长度为 d=q-p 的周期

之后我们辗转相减 就可以 \gcd(p,q) 也是周期了

后面的部分强化版也可以一样地证明 发现其实这个 p+q 的限制来源于字符串的边界使往前找一个周期超出串 S 范围了

\color{blue}\text{定理 3}

对于一个串每次跳最长 border 可以遍历他的所有 border

考虑 border 的定义 比较好理解 对同一个串 两个长度不同的 border 短的一定是长的的 border

\color{blue}\text{定理 4}

对于串 S,T ，若 2|T|\ge|S| ，则 T 在 S 中的匹配位置必为等差序列

对于出现次数小于 3 的必然成立 因为等差数列

考虑出现次数等于 3 次的

发现 T 有长度为 |T|-x 和 |T|-y 的 border 故有 x 和 y 的周期

因为 2|T|\ge |S| 所以 x+y\le |T|

由 WPL 得出 \gcd(x,y) 为 T 的周期

紫框都是 T 在 S 中出现的位置 与恰为 3 次矛盾

所以出现三次所成的等差数列必为 T 的最小周期

三次以上证明是一样的

\color{blue}\text{定理 5} 设 border 为 $|S|-x$ 有 $x\le \dfrac{|S|}{2}$ 直接 WPL 可以知道所成的等差数列公差为 $S$ 最小周期 $\color{blue}\text{定理 6} S$ 的所有 border 长度构成 $O(\log|S|)$ 个等差序列 更紧的上界是 $\lceil\log_2|S|\rceil

市面上的证明是这样的

对于 L\ge \dfrac{|S|}{2} 的一定都在同一个等差数列里

考虑这里面最短的 border T 满足 |T|\le \dfrac{3}{4}|S|

先考虑最小周期 d 当 d\le\dfrac{1}{4}|S| 时 开头扔掉几个周期 border就可以做到 |T|\le \dfrac{3}{4}|S|

对于 d\ge \dfrac{1}{4}|S| 最长的 border 就满足

然后考虑短 border 是长 border 的 border 剩下的递归处理 T 即可

这样上界大概是 O(\log |S|) 的

这里应该还有一种搞法

每次还是 L\ge \dfrac{|S|}{2} 在一个等差数列里面

对于所有 L< \dfrac{|S|}{2} 的 考虑把其中最大的作为新串考虑 设长度为 m 对于 \dfrac{|S|}{4}\le L<\dfrac{|S|}{2} 的 比最大的小的一定都是最大的的 border 考虑这些最大的有最小周期 p 所以这部分 border 成等差数列 m,m-p,m-2p \dots

这样上界严格是 \lceil\log_2|S|\rceil 的

感觉这个并不难想 和市面上那个证法就差一点 但看起来市面上抄来抄去的很神秘

金策大爷有个倍增搞法跟这个其实差不多的

定义 PS(S,T) (Prefix-Suffix) 为 |S|=|T| 同时为 S 的前缀且为 T 的后缀的串的集合

在定义 LargePS(S,T) 为当所有长度过半的 PS(S,T) 的子集

回到原命题

我们考虑 LargePS(s[1,2^k],s[n-2^k+1,n]) 发现 S 的所有 border 被倍增分组了

而对于一组 LargePS(s[1,2^k],s[n-2^k+1,n]) 其中最短的 border 一定不短于最长的 border 的一半

和第二种证法基本是一样的 只是引入了一个 PS 的概念

border 是单串的 PS 涉及两个串是 border 的拓展

将 border 按长度倍增分组很有用