Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
On the Maximal Sum of Exponents of Runsin a String
verfasst von : Maxime Crochemore, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition
v
with a period
p
such that 2
p
≤ |
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 2
n
.