Understanding Maximal Repetitions in Strings

Maxime Crochemore & Lucian Ilie
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.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.