On the Maximal Sum of Exponents of Runs in a String

Maxime Crochemore (1, 2) , Marcin Kubica (3) , Jakub Radoszewski (3) , Wojciech Rytter (3) , Tomasz Walen (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Informatics
3 Institute of Informatics [Warsaw]

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.

Domaines: Algorithme et structure de données [cs.DS]

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, 2012, 14 (-), pp.29-36. ⟨hal-00742081⟩