Understanding Maximal Repetitions in Strings

Authors Maxime Crochemore, Lucian Ilie



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1344.pdf
  • Filesize: 145 kB
  • 6 pages

Document Identifiers

Author Details

Maxime Crochemore
Lucian Ilie

Cite AsGet BibTex

Maxime Crochemore and Lucian Ilie. Understanding Maximal Repetitions in Strings. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 11-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1344

Abstract

The cornerstone of any algorithm computing all repetitions in a string of length $n$ in ${mathcal O(n)$ time is the fact that the number of runs (or maximal repetitions) is ${mathcal O(n)$. We give a simple proof of this result. As a consequence of our approach, the stronger result concerning the linearity of the sum of exponents of all runs follows easily.
Keywords
  • Combinatorics on words
  • repetitions in strings
  • runs
  • maximal repetitions
  • maximal periodicities
  • sum of exponents

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail