How many runs can a string contain?
Given a string x = x[1..n], a repetition of period p in x is a substring u(r) = x[i + 1..i + rp], p =vertical bar u vertical bar, 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 Theta(n log n). A run or maximal periodicity of period p in x is a substring u(r)t = X[i + 1..i + rp+ vertical bar t vertical bar] of x, where u(r) 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+ vertical bar t vertical bar +1. In 2000 Kolpakov and Kucherov showed that the maximum number rho(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 conjecture: rho(n) < n. Recently, Rytter [Wojciech Rytter, The number of runs in a string: Improved analysis of the linear upper bound, in: B. Durand, W. Thomas (Eds.), STACS 2006, in: Lecture Notes in Computer Science, vol. 3884, Springer-Verlag, Berlin, 2006, pp. 184-195] made a significant step toward proving this conjecture by showing that rho(n) < 5n. In this paper we improve Rytter's approach and press the bound on rho(n) further, proving rho(n) <= 3.48n. Crown Copyright (c) 2008 Published by Elsevier B.V. All rights reserved.
run string repetition periodicity