Finding maximal repetitions in a world in linear time

Roman Kolpakov, Gregory Kucherov

    Research output: Contribution to journalConference articlepeer-review

    260 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)596-604
    Number of pages9
    JournalAnnual Symposium on Foundations of Computer Science - Proceedings
    Publication statusPublished - 1999
    EventProceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA
    Duration: 17 Oct 199919 Oct 1999

    Cite this