LIPIcs.STACS.2008.1344.pdf
- Filesize: 145 kB
- 6 pages
Document
Understanding Maximal Repetitions in Strings
Authors
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
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
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)
0PDF Downloads