Understanding maximal repetitions in strings

Simple item page
dc.creatorCrochemore, Maxime
dc.creatorIlie, Lucian
dc.date2008-02-20
dc.date.accessioned2026-07-07T09:21:59Z
dc.date.available2026-07-07T09:21:59Z
dc.descriptionThe 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.
dc.identifierhttps://arxiv.org/abs/0802.2829
dc.identifierhttp://arxiv.org/abs/0802.2829
dc.identifierDans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155222
dc.subjectData Structures and Algorithms
dc.subjectCombinatorics
dc.titleUnderstanding maximal repetitions in strings
dc.typetext

Files

Collections

arXiv