Understanding maximal repetitions in strings

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.

Keywords

Data Structures and Algorithms, Combinatorics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/155222

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0802.2829
 http://arxiv.org/abs/0802.2829
 Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)

Collections

arXiv