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 …