字符串：\(\text{border}\) 理论
\(\text{border}\) 具有非常多的理论与性质。
\(周期与\ \text{border}\ \text{的关系}\)
对于一个周期为 \(p\)，长度为 \(n\) 的字符串 \(s\)：存在公共前后缀使得 \((\lfloor\frac{n}{p}\rfloor-1) p+n\bmod p\)。
思考如下的字符串：
其具有一个 \(\text{border}\)：\(\tt BiliBiliBiliBiliBi\)。
由此得出：
对于一个周期为 \(p\)，长度为 \(n\) 的字符串 \(s\)：存在公共前后缀使得 \((\lfloor\frac{n}{p}\rfloor-1) p+n\bmod p\)。
进一步地，最长的周期对应公共前后缀，最短的周期对应最长公共前后缀，即 \(\text{border}\)。
证明：
周期的定义，对于所有的 \(1\leq i\leq n-p\)，\(S_i=S_{i+p}\)。
公共前后缀的定义，\(S[1,n-p]=S[1+p,n]\)，两个子串的字符位置差恰好为 \(p\)，因为 \(S_i=S_{i+p}\)，所以两者等价。
\(\text{弱周期引理}\)
对于字符串 \(S\) 且 \(|S|=n\)，存在长度为 \(p\) 与 \(q\) 的周期且 \(p\neq q,p+q\leq n\)，则 \(\gcd(p,q)\) 同为字符串的周期。
证明：
- 假设 \(p<q\)，设 \(d=q-p\)。对于 \(1\leq i\leq |S|\)，对于字符串的任意下标 \(x\)，若 \(x>p\)，则 \(S_x=S_{x_p}=S_{x-p+q}=S_{x+d}\)。
- 反之，若 \(x\leq p\)，则 \(S_x=S_{x+q}=S_{x+q-p}=S_{x+d}\)。
- 得 \(d\) 是 \(S\) 的一个周期，根据最大公约数的性质，可得 \(\text{gcd(p,q)}\) 同为 \(S\) 的周期。
\(\text{周期引理}\)
\(|S|=n\)，存在长度为 \(p\) 与 \(q\) 的周期且 \(p\neq q,p+q\leq n+\gcd(p,q)\)，则 \(\gcd(p,q)\) 同为字符串的周期。
证明略，使用生成函数等方法较为复杂。
\(\text{border}\ \text{的等差性}\)
我们定义字符串 \(S\) 的最小周期为 \(\text{per(S)}=p\)，另一个周期为 \(q\)，且 \(p,q\leq \frac{n}{2}\)。则所有的长度 \(len\) 满足 \(2len\geq |S|\) 的 \(\text{border}\) 长度构成等差数列。
证明：则由弱周期引理，\(\gcd(p,q)\) 为一个周期，又因为 \(p\) 是最小周期，所以 \(\gcd(p,q)\geq p\)。
又因为 \(\gcd(p,q)\leq p\)，\(\gcd(p,q)=p\)。
所以 \(q\) 为 \(p\) 的倍数。
我们注意到对于一个长度为 \(p\) 的周期，对于任意 \(kp\) 且 \(k\) 为正整数，字符串存在长度为 \(kp\) 的周期。
又因为 \(q=kp\) 恒成立，所以所有的 \(q\) 构成等差数列。
对应的，存在长度为 \(n-q\) 的 \(\text{border}\)，构成等差序列。
证毕。