2026-07-23T06:18:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12152 2024-03-06T10:49:26Z ddc:004 open_access

On Extensions of Maximal Repeats in Compressed Strings Pape-Lange, Julian Maximal repeats Extensions of maximal repeats Combinatorics on compressed strings LZ77 Burrows-Wheeler transform Burrows-Wheeler transform conjecture Compact suffix automata CDAWGs This paper provides upper bounds for several subsets of maximal repeats and maximal pairs in compressed strings and also presents a formerly unknown relationship between maximal pairs and the run-length Burrows-Wheeler transform. This relationship is used to obtain a different proof for the Burrows-Wheeler conjecture which has recently been proven by Kempa and Kociumaka in "Resolution of the Burrows-Wheeler Transform Conjecture". More formally, this paper proves that the run-length Burrows-Wheeler transform of a string S with z_S LZ77-factors has at most 73(log₂ |S|)(z_S+2)² runs, and if S does not contain q-th powers, the number of arcs in the compacted directed acyclic word graph of S is bounded from above by 18q(1+log_q |S|)(z_S+2)². Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian Pape-Lange 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.27 urn:nbn:de:0030-drops-121523 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.27 eng https://creativecommons.org/licenses/by/3.0/legalcode