2026-07-23T21:50:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11126 2024-03-06T10:47:30Z ddc:004 open_access

Repetition Detection in a Dynamic String Amir, Amihood Boneh, Itai Charalampopoulos, Panagiotis Kondratovsky, Eitan string algorithms dynamic algorithms squares repetitions runs A string UU for a non-empty string U is called a square. Squares have been well-studied both from a combinatorial and an algorithmic perspective. In this paper, we are the first to consider the problem of maintaining a representation of the squares in a dynamic string S of length at most n. We present an algorithm that updates this representation in n^o(1) time. This representation allows us to report a longest square-substring of S in O(1) time and all square-substrings of S in O(output) time. We achieve this by introducing a novel tool - maintaining prefix-suffix matches of two dynamic strings. We extend the above result to address the problem of maintaining a representation of all runs (maximal repetitions) of the string. Runs are known to capture the periodic structure of a string, and, as an application, we show that our representation of runs allows us to efficiently answer periodicity queries for substrings of a dynamic string. These queries have proven useful in static pattern matching problems and our techniques have the potential of offering solutions to these problems in a dynamic text setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amihood Amir and Itai Boneh and Panagiotis Charalampopoulos and Eitan Kondratovsky 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.5 urn:nbn:de:0030-drops-111265 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.5 eng https://creativecommons.org/licenses/by/3.0/legalcode