周期引理

若字符串 $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$ 的周期。