10.4230/LIPIcs.STACS.2008.1344
Crochemore, Maxime
Ilie, Lucian
Understanding Maximal Repetitions in Strings
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
2008
Computer Science
000 Computer science, knowledge, general works
Herbstritt, Marc
2008-02-06
eng
ConferencePaper
6 pages
application/pdf
1.0
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC-BY-NC-ND)
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.