AbstractGiven a string x=x[1..n], a repetition of period p in x is a substring ur=x[i+1..i+rp], p=∣u∣, r≥2, where neither u=x[i+1..i+p] nor x[i+1..i+(r+1)p+1] is a repetition. The maximum number of repetitions in any string x is well known to be Θ(nlogn). A run or maximal periodicity of period p in x is a substring urt=x[i+1..i+rp+∣t∣] of x, where ur is a repetition, t a proper prefix of u, and no repetition of period p begins at position i of x or ends at position i+rp+∣t∣+1.In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n) of runs in any string x[1..n] is O(n), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data to prompt the conjectur...