周期引理及其证明

b6e0_ · 2024-04-25 15:08:32 · 算法·理论

引理内容：若长度为 n 的字符串 s 有 p,q(1\le p,q\le n) 的周期，记 g=\gcd(p,q)，若 p+q\le n+g，则 s 有 g 的周期。

证明：不妨设 p\le q。首先，若 g=p，那么直接不用证了，所以不妨设 g\ne p，则有 2g\le p<q。

首先，因为 p+g\le q，所以 2p+g\le p+q\le n+g，所以 2p\le n。

令 d=q-p，有 0<g\le d。

运用归纳法，假设周期引理对于所有长度 <n 的字符串成立。

又因为 n-q+d=n-p，所以 s 的长度为 n-p 的前缀和后缀都有 d 的周期。下面尝试运用归纳假设证明 s 的长度为 n-p 的前后缀都有 g 的周期。需要满足的条件都可以被证明：

• 显然 \gcd(p,d)=g；
• 因为 2p\le n，所以 p\le n-p；因为 q\le n，所以 q-p=d\le n-p；

因为 g\le d，所以 \forall i\le n-q 或 i>p，若 i+g\le n，则 s_i=s_{i+g}。

现在我们离证明 s 有 g 的周期还差 (n-q,p] 这一段。

这一段的长度为 p+q-n，小于等于 g。

所以，\forall n-q<i\le p,s_i=s_{i-g},s_{i+g}=s_{i+g-p}。

因为 p\ge 2g，所以 i+g-p\le i-g，所以 i-g,i+g-p 都 \le n-q。另一方面，这两个位置的差 p-2g 是 g 的倍数，所以 s_{i-g}=s_{i+g-p}，所以 s_i=s_{i+g}，得证。