2026-07-23T05:31:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10489 2024-03-06T10:45:51Z ddc:004 open_access

On Maximal Repeats in Compressed Strings Pape-Lange, Julian Maximal repeats Combinatorics on compressed strings LZ77 Compact suffix automata CDAWGs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian Pape-Lange 2019 Is Part Of LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2019.18 urn:nbn:de:0030-drops-104898 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.18 eng https://creativecommons.org/licenses/by/3.0/legalcode