10.4230/LIPICS.STACS.2008.1344
Crochemore, Maxime
Maxime
Crochemore
Ilie, Lucian
Lucian
Ilie
Understanding Maximal Repetitions in Strings
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Combinatorics on words
repetitions in strings
runs
maximal repetitions
maximal periodicities
sum of exponents
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13442
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
2
11
16
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
6 pages
148889 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 11-16