字符串随记

一、Border 和周期

1. 对于字符串 \(S\)，若其最小整周期不为 \(|S|\)，则最小整周期为最小周期。

证明：考虑反证法。易知最小整周期 \(p \le \frac{|S|}{2}\)。若存在周期 \(q < p\)，则根据 Weak Periodicity Lemma 可知 \(\gcd(p, q)\) 为一更小的整周期，矛盾。