2026-07-25T13:34:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20113 2024-06-18T13:20:58Z ddc:004 open_access

Maintaining the Size of LZ77 on Semi-Dynamic Strings Bannai, Hideo Charalampopoulos, Panagiotis Radoszewski, Jakub Lempel-Ziv compression LZ77 semi-dynamic algorithm cyclic rotation We consider the problem of maintaining the size of the LZ77 factorization of a string S of length at most n under the following operations: (a) appending a given letter to S and (b) deleting the first letter of S. Our main result is an algorithm for this problem with amortized update time Õ(√n). As a corollary, we obtain an Õ(n√n)-time algorithm for computing the most LZ77-compressible rotation of a length-n string - a naive approach for this problem would compute the LZ77 factorization of each possible rotation and would thus take quadratic time in the worst case. We also show an Ω(√n) lower bound for the additive sensitivity of LZ77 with respect to the rotation operation. Our algorithm employs dynamic trees to maintain the longest-previous-factor array information and depends on periodicity-based arguments that bound the number of the required updates and enable their efficient computation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hideo Bannai and Panagiotis Charalampopoulos and Jakub Radoszewski 2024 Is Part Of LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2024.3 urn:nbn:de:0030-drops-201134 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.3 eng https://creativecommons.org/licenses/by/4.0/legalcode