Home
Scholarly Works
Understanding maximal repetitions in strings
Preprint

Understanding maximal repetitions in strings

Abstract

The cornerstone of any algorithm computing all repetitions in a string of length n in O(n) time is the fact that the number of runs (or maximal repetitions) is 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.

Authors

Crochemore M; Ilie L

Publication date

February 20, 2008

DOI

10.48550/arxiv.0802.2829

Preprint server

arXiv

Labels

View published work (Non-McMaster Users)

Contact the Experts team