Understanding maximal repetitions in strings

DOI10.4230/LIPICS.STACS.2008.1344MaRDI QIDQ4910702zbMATH OpenFDO

Authors Maxime Crochemore, Lucian Ilie

Publication date 19 March 2013

Full work available at URL https://arxiv.org/abs/0802.2829, http://subs.emis.de/LIPIcs/frontdoor_5371.html

zbMATH Keywords

combinatorics on wordsmaximal periodicitiesmaximal repetitionsrepetitions in stringsrunssum of exponents

Mathematics Subject Classification ID

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

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.

Recommendations

• Maximal repetitions in strings
• Analysis of Maximal Repetitions in Strings
• The runs theorem and beyond
• The ``runs theorem
• Almost linear time computation of maximal repetitions in run length encoded strings

Cited in

(7)

• Repetitions in strings: algorithms and combinatorics
• Large-scale detection of repetitions
• Analysis of Maximal Repetitions in Strings
• scientific article; zbMATH DE number 2051171 (Why is no real title available?)
• Two-dimensional maximal repetitions
• Repetition Detection in a Dynamic String
• Maximal repetitions in strings

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)