Maximal Repetitions in Words or How to Find all Squares in Linear Time

Roman Kolpakov 1 Gregory Kucherov 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A (fractional) 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 count the exact number of maximal repetitions in Fibonacci words. Then we prove our main result asserting that the maximal number of such repetitions in general words (on arbitrary alphabet) is linear in the length. We then show how this result implies a linear-time algorithm for finding all maximal repetitions.
Type de document :
Rapport
[Intern report] 98-R-227 || kolpakov98b, 1998, 22 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00098737
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:22:02
Dernière modification le : mardi 6 mars 2018 - 17:40:58
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 11:34:11

Fichiers

Identifiants

  • HAL Id : inria-00098737, version 1

Collections

Citation

Roman Kolpakov, Gregory Kucherov. Maximal Repetitions in Words or How to Find all Squares in Linear Time. [Intern report] 98-R-227 || kolpakov98b, 1998, 22 p. 〈inria-00098737〉

Partager

Métriques

Consultations de la notice

162

Téléchargements de fichiers

62