周期引理

若字符串 $s$ 有周期 $p,q$，且 $p+q\le|s|+\gcd(p,q)$，则 $\gcd(p,q)$ 为 $|s|$ 的周期。

---

若 $p=q$，结论显然。否则设 $p>q$。

考虑归纳地证明。因为 $(p-q)+q\le|s|-q+\gcd(p-q,q)$，如果周期引理对于 $s$ 长为 $|s|-q$ 的后缀成立，那么 $\gcd(p-q,q)$ 是该后缀的一个周期。

又因为 $2q\le p-\gcd(p,q)+q\le|s|$，即该后缀长度不少于 $\gcd(p,q)$，所以 $\gcd(p-q,q)$ 是该后缀的周期，也就为 $s$ 长为 $q$ 的前缀的周期，并且是整周期。

所以 $\gcd(p,q)$ 为 $s$ 的周期。