How many runs can a string contain?
MetadataShow full item record
In 2000 Kolpakov and Kucherov showed that the maximum number ρ(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: ρ(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. In this paper we improve Rytter’s approach and press the bound on ρ(n) further, proving ρ(n)≤3.48n.
The link to the journal’s home page is: http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description
Copyright © 2008 Elsevier Ltd. All rights reserved
Showing items related by title, author, creator and subject.
Smith, S.; Rasouli, Vamegh (2012)Drilling deviated and horizontal wells is commonly used in oil and gas industry for different purposes. In particular in unconventional reservoirs such as gas shales or tight formations horizontal wellbores provide a ...
Selected Physical Characteristics and Playing-Related Musculoskeletal Problems in Adolescent String InstrumentalistsVinci, S.; Smith, A.; Ranelli, Sonia (2015)PURPOSE: Music research has investigated the prevalence of playing-related musculoskeletal problems in adults and children, but the prevalence in adolescents has not been established. String instrumentalists report high ...
Franek, F.; Smyth, Bill (2004)Recently, several authors presented linear recursive algorithms for sorting suffixes of a string. All these algorithms employ a similar three-step approach, based on an initial division of the suffixes of x into two sets: ...