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: https://drops.dagstuhl.de/opus/volltexte/2019/10489/
Go to the corresponding LIPIcs Volume Portal


Pape-Lange, Julian

On Maximal Repeats in Compressed Strings

pdf-format:
LIPIcs-CPM-2019-18.pdf (0.5 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI