Skip to Main content Skip to Navigation
Journal articles

Repetitions in strings: algorithms and combinatorics

Abstract : The article is an overview of basic issues related to repetitions in strings, concentrating on algorithmic and combinatorial aspects. This area is important both from theoretical and practical point of view. Repetitions are highly periodic factors (substrings) in strings and are related to periodicities, regularities, and compression. The repetitive structure of strings leads to higher compression rates, and conversely, some compression techniques are at the core of fast algorithms for detecting repetitions. There are several types of repetitions in strings: squares, cubes, and maximal repetitions also called runs. For these repetitions, we distinguish between the factors (sometimes qualified as distinct) and their occurrences (also called positioned factors). The combinatorics of repetitions is a very intricate area, full of open problems. For example we know that the number of (distinct) primitively-rooted squares in a string of length n is no more than 2n−Θ(log n), conjecture to be n, and that their number of occurrences can be Θ(n log n). Similarly we know that there are at most 1.029n and at least 0.944n maximal repetitions and the conjecture is again that the exact bound is n. We know almost everything about the repetitions in Sturmian words, but despite the simplicity of these words, the results are nontrivial. One of the main motivations for writing this text is the development during the last couple of years of new techniques and results about repetitions. We report both the progress which has been achieved and which we expect to happen.
Document type :
Journal articles
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00741884
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 11:32:17 AM
Last modification on : Monday, June 8, 2020 - 10:54:02 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:04 AM

File

Repetitions_in_strings_algorit...
Files produced by the author(s)

Identifiers

Citation

Maxime Crochemore, Lucian Ilie, Wojciech Rytter. Repetitions in strings: algorithms and combinatorics. Theoretical Computer Science, Elsevier, 2009, 410 (50), pp.5227-5235. ⟨10.1016/j.tcs.2009.08.024⟩. ⟨hal-00741884⟩

Share

Metrics

Record views

367

Files downloads

4780