How many runs can a string contain?
Puglisi, S.J., Simpson, J. and Smyth, W.F. (2008) How many runs can a string contain? Theoretical Computer Science, 401 (1-3). pp. 165-171.
*Subscription may be required
Given a string x=x[1..n], a repetition of period pp in x is a substring ur=x[i+1..i+rp], p=∣u∣, r≥2r≥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)Θ(nlogn). A run or maximal periodicity of period pp 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 pp begins at position ii of x or ends at position i+rp+∣t∣+1.
In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n)ρ(n) of runs in any string x[1..n] is O(n)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: ρ(n)<nρ(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 ρ(n)<5nρ(n)<5n. In this paper we improve Rytter’s approach and press the bound on ρ(n)ρ(n) further, proving ρ(n)≤3.48nρ(n)≤3.48n.
|Publication Type:||Journal Article|
|Copyright:||© 2008 Published by Elsevier B.V.|
|Item Control Page|
Downloads per month over past year