Skip to Main content Skip to Navigation
Conference papers

The maximal number of cubic runs in a string

Abstract : A run is an inclusion maximal occurrence in a string (as a subinterval) of a factor in which the period repeats at least twice. The maximal number of runs in a string of length n has been thoroughly studied, and is known to be between 0.944n and 1.029n. The proofs are very technical. In this paper we investigate cubic runs, in which the period repeats at least three times. We show the upper bound on their maximal number, cubic-runs(n), in a string of length n: cubic-runs(n)<0.5n. The proof of linearity of cubic-runs(n) utilizes only simple properties of Lyndon words and is considerably simpler than the corresponding proof for general runs. For binary strings, we provide a better upper bound cubic-runs_2(n)<0.48n which requires computer-assisted verification of a large number of cases. We also construct an infinite sequence of words over binary alphabet for which the lower bound is 0.41n.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

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

File

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

Identifiers

  • HAL Id : hal-00742037, version 1

Citation

Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, et al.. The maximal number of cubic runs in a string. LATA, 2010, Trier, Germany. pp.227-238. ⟨hal-00742037⟩

Share

Metrics

Record views

262

Files downloads

284