Finding Maximal Repetitions in a Word in Linear Time

Roman Kolpakov Gregory 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 $w$ is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in $w$, that is those for which any extended subword of $w$ has a bigger period. The set of such repetitions represents in a compact way all repetitions in $w$. We first prove a combinatorial result asserting that the sum of exponents of all maximal repetitions of a word of length $n$ 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. This allows us to construct a linear-time algorithm for finding all maximal repetitions. Some consequences and applications of these results are discussed, as well as related works.
Type de document :
Communication dans un congrès
1999 Symposium on Foundations of Computer Science - FOCS'99, 1999, New-York, USA, IEEE Computer Society, pp.596--604, 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00098853
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:39:18
Dernière modification le : mardi 6 mars 2018 - 17:40:58

Identifiants

  • HAL Id : inria-00098853, version 1

Collections

Citation

Roman Kolpakov, Gregory Kucherov. Finding Maximal Repetitions in a Word in Linear Time. 1999 Symposium on Foundations of Computer Science - FOCS'99, 1999, New-York, USA, IEEE Computer Society, pp.596--604, 1999. 〈inria-00098853〉

Partager

Métriques

Consultations de la notice

172