On Maximal Repetitions in Words

Roman Kolpakov 1 Grégory Kucherov 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A repetition in a word is a subword with the period at most half of the subword length. We study maximal repetitions occurring in a word, that is those for which any extended subword has a bigger period. The set of such repetitions represents in a compact way all repetitions in the word. We first study maximal repetitions in Fibonacci words -- we count their exact number, and estimate the sum of their exponents. These quantities turn out to be linearly-bounded in the length of the word. We then prove that the sum of exponents of all maximal repetitions in general words of length $n$ (over arbitrary alphabet) is bounded by a linear function in $n$. This implies, in particular, that there is only a linear number of maximal repetitions in a word. We then discuss some algorithmic applications of this result. In particular, we present a linear-time algorithm for finding all maximal repetitions in a word.
Type de document :
Article dans une revue
Journal on Discrete Algorithms, 2000, 1 (1), pp.159-186
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:50:53
Dernière modification le : mardi 6 mars 2018 - 17:40:58


  • HAL Id : inria-00099092, version 1



Roman Kolpakov, Grégory Kucherov. On Maximal Repetitions in Words. Journal on Discrete Algorithms, 2000, 1 (1), pp.159-186. 〈inria-00099092〉



Consultations de la notice