Understanding maximal repetitions in strings

DOI10.4230/LIPICS.STACS.2008.1344zbMATH Open1259.68249arXiv0802.2829MaRDI QIDQ4910702

M. Crochemore, Lucian Ilie

Publication date: 19 March 2013

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.

Full work available at URL: https://arxiv.org/abs/0802.2829

zbMATH Keywords

combinatorics on wordsrunsmaximal periodicitiesrepetitions in stringsmaximal repetitionssum of exponents

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (1)

Repetition Detection in a Dynamic String

This page was built for publication: Understanding maximal repetitions in strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4910702)