A New Periodicity Lemma

Given a string x = x[1..n], a repetition of period p in x is a substring ur = x[i..i + rp − 1], p = |u|, r ≥ 2, where neither u = x[i..i + p − 1] nor x[i..i + (r + 1)p − 1] is a repetition. The maximum number of repetitions in any string x is well known to be Θ(nlog n). A run or maximal periodicity of period p in x is a substring urt = x[i..i + rp + |t| − 1] of x, where ur is a repetition, t a proper prefix of x, and no repetition of period p begins at position i – 1 of x or ends at position i + rp + |t|. In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n) of runs in any string x is O(n), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data strongly suggesting that ρ(n) < n. In this paper, as a first step toward proving this conjecture, we present a periodicity lemma that establishes limitations on the number of squares, and their periods, that can occur over a specified range of positions in x. We then apply this result to specify corresponding limitations on the occurrence of runs.