License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2019.18
URN: urn:nbn:de:0030-drops-104898
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10489/
Pape-Lange, Julian
On Maximal Repeats in Compressed Strings
Abstract
This paper presents and proves a new non-trivial upper bound on the number of maximal repeats of compressed strings. Using Theorem 1 of Raffinot's article "On Maximal Repeats in Strings", this upper bound can be directly translated into an upper bound on the number of nodes in the Compacted Directed Acyclic Word Graphs of compressed strings.
More formally, this paper proves that the number of maximal repeats in a string with z (self-referential) LZ77-factors and without q-th powers is at most 3q(z+1)^3-2. Also, this paper proves that for 2000 <= z <= q this upper bound is tight up to a constant factor.
BibTeX - Entry
@InProceedings{papelange:LIPIcs:2019:10489,
author = {Julian Pape-Lange},
title = {{On Maximal Repeats in Compressed Strings}},
booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
pages = {18:1--18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-103-0},
ISSN = {1868-8969},
year = {2019},
volume = {128},
editor = {Nadia Pisanti and Solon P. Pissis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10489},
URN = {urn:nbn:de:0030-drops-104898},
doi = {10.4230/LIPIcs.CPM.2019.18},
annote = {Keywords: Maximal repeats, Combinatorics on compressed strings, LZ77, Compact suffix automata, CDAWGs}
}
|
Keywords: |
|
Maximal repeats, Combinatorics on compressed strings, LZ77, Compact suffix automata, CDAWGs |
|
Collection: |
|
30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.06.2019 |
