Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Maximal repetitions in strings

Abstract : The cornerstone of any algorithm computing all repetitions in strings of length n in O(n) time is the fact that the number of maximal repetitions (runs) is linear. Therefore, the most important part of the analysis of the running time of such algorithms is counting the number of runs. Kolpakov and Kucherov [FOCS'99] proved it to be cn but could not provide any value for c. Recently, Rytter [STACS'06] proved that c ≤ 5. His analysis has been improved by Puglisi et al. to obtain 3.48 and by Rytter to 3.44 (both submitted). The conjecture of Kolpakov and Kucherov, supported by computations, is that c = 1. Here we improve dramatically the previous results by proving that c ≤ 1.6 and show how it could be improved by computer verification down to 1.18 or less. While the conjecture may be very difficult to prove, we believe that our work provides a good approximation for all practical purposes. For the stronger result concerning the linearity of the sum of exponents, we give the first explicit bound: 5.6n. Kolpakov and Kucherov did not have any and Rytter considered "unsatisfactory" the bound that could be deduced from his proof. Our bound could be as well improved by computer verification down to 2.9n or less.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 6:49:49 PM
Last modification on : Saturday, January 15, 2022 - 3:58:16 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:35 AM


Files produced by the author(s)



Maxime Crochemore, Lucian Ilie. Maximal repetitions in strings. Journal of Computer and System Sciences, Elsevier, 2008, 74 (10.1016/j.jcss.2007.09.003), pp.796-807. ⟨10.1016/j.jcss.2007.09.003⟩. ⟨hal-00619712⟩



Record views


Files downloads