字符串 I：border 理论 I

字符串：\(\text{border}\) 理论

\(\text{border}\) 具有非常多的理论与性质。

\(周期与\ \text{border}\ \text{的关系}\)

对于一个周期为 \(p\)，长度为 \(n\) 的字符串 \(s\)：存在公共前后缀使得 \((\lfloor\frac{n}{p}\rfloor-1) p+n\bmod p\)。

思考如下的字符串：

\[\tt BiliBiliBiliBiliBi \]

其具有一个 \(\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}\)，构成等差序列。

证毕。