A New Periodicity Lemma

Given a string $\s{x}=\s{x}[1..n]$, a repetition of period p in {\mbox{\boldmath x}} is a substring ${\mbox{\boldmath u}}^r = \break {\mbox{\boldmath x}}[i..i\+ rp\- 1]$, $p = |{\mbox{\boldmath u}}|$, $r \ge 2$, where neither ${\mbox{\boldmath u}} = {\mbox{\boldmath x}}[i..i\+ p\- 1]$ nor ${\mbox{\boldmath x}}[i..i\+ (r\+ 1)p\- 1]$ is a repetition. The maximum number of repetitions in any string {\mbox{\boldmath x}} is well known to be …