HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

On Maximal Repetitions in Words

Roman Kolpakov 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 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 maximal number of maximal repetitions in general words (on arbitrary alphabet) of length $n$ is linearly-bounded in $n$, and we mention some applications and consequences of this result.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/inria-00098852
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:39:16 AM
Last modification on : Friday, February 4, 2022 - 3:30:23 AM

Identifiers

  • HAL Id : inria-00098852, version 1

Collections

Citation

Roman Kolpakov, Gregory Kucherov. On Maximal Repetitions in Words. 12th International Symposium on Fundamentals of Computation Theory - FCT'99, 1999, Iasi Romania, pp.374 -- 385. ⟨inria-00098852⟩

Share

Metrics

Record views

51