Skip to Main content Skip to Navigation
Journal articles

On the Maximal Sum of Exponents of Runs in a String

Abstract : A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p ≤ |v|. The exponent of a run is defined as |v|/p and is ≥ 2. We show new bounds on the maximal sum of exponents of runs in a string of length n. Our upper bound of 4.1 n is better than the best previously known proven bound of 5.6 n by Crochemore & Ilie (2008). The lower bound of 2.035 n, obtained using a family of binary words, contradicts the conjecture of Kolpakov & Kucherov (1999) that the maximal sum of exponents of runs in a string of length n is smaller than 2n.
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00742081
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 2:18:03 AM
Last modification on : Monday, June 8, 2020 - 10:54:02 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:29 AM

File

On_the_maximal_sum_of_exponent...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00742081, version 1

Citation

Maxime Crochemore, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen. On the Maximal Sum of Exponents of Runs in a String. Journal of Discrete Algorithms, Elsevier, 2012, 14 (-), pp.29-36. ⟨hal-00742081⟩

Share

Metrics

Record views

682

Files downloads

372