How many runs can a string contain?

S.J. Puglisi; J. Simpson; W.F. Smyth

doi:10.1016/j.tcs.2008.04.020

Back

Journal article

Open access

Peer reviewed

How many runs can a string contain?

S.J. Puglisi, J. Simpson and W.F. Smyth

Theoretical Computer Science, Vol.401(1-3), pp.165-171

2008

DOI: https://doi.org/10.1016/j.tcs.2008.04.020

Files and links (2)

pdf

RunsInStrings.pdfDownload View

Author’s Version Open Access

url

Link to Published Version *Subscription may be requiredView

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.

Details

Title: How many runs can a string contain?
Authors/Creators: S.J. Puglisi (Author/Creator) - RMIT University
J. Simpson (Author/Creator) - Curtin University
W.F. Smyth (Author/Creator) - Curtin University
Publication Details: Theoretical Computer Science, Vol.401(1-3), pp.165-171
Publisher: Elsevier BV
Identifiers: 991005543215607891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article

Metrics

188 File views/ downloads

107 Record Views

43 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1103 Efficient Algorithms
Web Of Science research areas: Computer Science, Theory & Methods
ESI research areas: Computer Science