• 若 $1\leq r\leq |S|$，$S_{1..r}=S_{|S|-r+1..|S|}$，则称 $S_{1..r}$ 是 $S$ 的 $border$，长度为 $r$。
• $border$ 的性质：字符串 $s$ 的所有 $border$ 长度排序后可分成不超过 $\log_2 |S|$ 段，每段是一个等差数列。
• 引理 $1$：若存在一个 $border$ 长度为 $k$ ，那么 $|S|-k$ 为 $S$ 的一个周期。
• 引理 $2$：若 $p,q$ 为 $S$ 的周期，且 $p+q\leq |S|$，那么 $\gcd(p,q)$ 也为$S$ 的周期。
• 引理 $3$：$S$ 的所有 $\geq\frac{|S|}{2}$ 的 $border$ 长度组成一个等差数列。

Proof

• 引理 $1$ 是显然的，根据定义，对于 $i+|S|-k\leq |S|$ 即 $i\leq k$，有 $S[i]=S[i+(|S|-k)]$。
• 引理 $2$ [^1]
  • 设 $p < q,d=q-p$
  • 若 $|S|-q\leq i\leq |S|-d$，$S_i=S_{i-p}=S_{i-p+q}=S_{i+d}$。
  • 若 $0\leq i < |S|-q$，$S_i=S_{i+p}=S_{i+q-p}=S_{i+d}$。
  • 那么 $d=q-p$ 也为 $S$ 的周期。由欧几里得算法可知 $\gcd(p,q)$ 也为 $S$ 的周期。
• 引理 $3$ [^2]
  • 设 $S$ 长度最大的 $border$ 的长度为 $n-p,(p\leq \frac{|S|}2)$。
  • 设另外某个 $border$ 的长度为 $n-q,(q\leq \frac{|S|}2)$。
  • 由引理 $2$，有 $\gcd(p,q)$ 是 $S$ 的周期，那么 $n-\gcd(p,q)$ 是 $s$ 的 $border$ 的长度。
  • 则有 $n-p\geq n-\gcd(p,q)$，于是 $\gcd(p,q)\geq p$，即 $p\mid q$。
• 根据引理 $3$，有：
• 考虑更小的 $border$，对其进行按长度的二进制分组，即 $[1,2),[2,4),[4,8)\cdots,[2^k,n)$ 各分为一类。
• 对于在某个类中的 $border$，考虑其最长的，那么剩下的所有 $border$ 一定是最长的那个 $border$ 的 $border$。（正确性证明类似于 $kmp$）。
• 故以最长的 $border$ 为母串（称之为$T$），而类内所有 $border$ 的长度必定 $>\frac{|T|}2$。根据引理 $3$ ，故一类的 $border$ 长度为一个等差数列。
• 故字符串 $S$ 的所有 $border$ 能划分成 $\log_2 S$ 个等差数列。

参考文献：

1. 钟子谦，《串串 解题报告》引理 5.1，2019 年信息学奥林匹克中国国家集训队队员作业
2. 金策，《字符串算法选讲》Border的结构，WC2017课件