Maximal Repetitions in Words or How to Find all Squares in Linear Time - Archive ouverte HAL Access content directly
Reports Year : 1998

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

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.
Fichier principal
Vignette du fichier
98-R-227.pdf (324.69 Ko) Télécharger le fichier

Dates and versions

inria-00098737 , version 1 (26-09-2006)

Identifiers

  • HAL Id : inria-00098737 , version 1

Cite

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⟩
105 View
56 Download

Share

Gmail Facebook Twitter LinkedIn More