Border 与周期

一个字符串的一个 Border, 是指它的一个真前缀, 这个真前缀与它的同样长度的真后缀完全相同. 同时, 有时也指某个 Border 的长度.

一个长度为 $n$ 的字符串 $s$ 的周期, 是指一个整数 $k(1\le k < n)$, 使得 $\forall i\in [n - k], \text{有 }s_i = s_{i+k}$. 同时, 有时也指长度为 $k$ 的前缀或后缀. 真周期是说一个周期同时还整除 $n$.

不难发现, 一个周期的补是一个 Border, 一个 Border 的补是一个周期. 所以, 研究周期就是研究 Border, 研究 Border 就是研究周期.

弱周期引理(Weak Periodicity Lemma)

如果长度为 $n$ 的字符串 $s$ 有两个周期 $a, b(a < b)$, 这两个周期会产生什么相互作用呢?

弱周期引理:

对于 $s$ 的两个周期 $a, b$, 如果 $a + b \le n$, 那么 $\gcd(a, b)$ 也是 $s$ 的一个周期.

这是因为, 如果 $a + b\le n$, 那么 $\forall i\in [n - b + a], \text{有 } i + b\le n \lor i - a\ge 1$, 所以要么 $s_i = s_{i + b} = s_{i + b - a}$, 要么 $s_i = s_{i - a} = s_{i - a + b}$, 所以 $b - a$ 也是 $s$ 的一个周期.

显然, 运用数学归纳法, 结合欧几里得算法的知识, 不难证明 $\gcd(a, b)$ 也是 $s$ 的一个周期.

(强)周期引理((Strong) Periodicity Lemma)

强周期引理改进了上述定理中不等式的界.

(强)周期引理:

对于 $s$ 的两个周期 $a, b$, 如果 $a + b - \gcd(a, b) \le n$, 那么 $\gcd(a, b)$ 也是 $s$ 的一个周期.

强周期引理有许多证明方法. 这里给出最简单的一个.

考虑将 $\mathbb{Z}^+$ 按照 ${} \bmod a$ 的余数分为 $a$ 类. 考虑另一个周期 $b$, 即对于所有 $i \in [n - b]$, 将等价类 $i \bmod a$ 和 $(i + b) \bmod a$ 合并.

如果 $n$ 充分大, 最终只会剩下 $\gcd(a, b)$ 个等价类, 这正是弱周期引理向我们指出的. 强周期引理即考虑使等价类个缩减至 $\gcd(a, b)$ 的最小 $n$.

因为每次合并至多使等价类的个数减少 $1$, 所以 $n - b \ge a - \gcd(a, b)$, 所以 $n \ge a + b - \gcd(a, b)$. 这是答案的一个下界.

将 $\mathbb{Z}\cap[0, a)$ 按照 ${} \bmod \gcd(a, b)$ 的余数分类. 考虑在 $x$ 与 $(x + b) \bmod a$ 之间连边, 这样, 每个 ${} \bmod \gcd(a, b)$ 的等价类内部的连边会形成一个环, 环的大小即 $\frac{a}{\gcd(a, b)}$.

现在, 对于所有 $i\in [a + b - \gcd(a, b) - b] = [a - \gcd(a, b)]$, 将 $i \bmod a$ 和 $(i + b) \bmod a$ 对应的边合并. 显然, 在每个环上这等同于从一条边开始依次向后合并, 总的合并次数是 $\frac{a - \gcd(a, b)}{\gcd(a, b)} = \frac{a}{\gcd(a, b)} - 1$. 所以这样以后, 每个环都被合并为了一个点. 所以得证.