The “runs” conjecture, proposed by Kolpakov and Kucherov (1999) [7], states that the number of occurrences of maximal repetitions (runs) in a string of length n, runs(n), is at most n. We almost solve the conjecture by proving that runs(n)⩽1.029n. This bound is obtained using a combination of theory and computer verification.
Authors
Crochemore M; Ilie L; Tinta L
Journal
Theoretical Computer Science, Vol. 412, No. 27, pp. 2931–2941