Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

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.  Preview
PDF - Authors' Version
*Subscription may be required

Abstract

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. Item Control Page