文章基本信息

标题：Repetition Detection in a Dynamic String
本地全文：下载
作者：Amihood Amir ; Itai Boneh ; Panagiotis Charalampopoulos 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：144
页码：1-18
DOI：10.4230/LIPIcs.ESA.2019.5
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：string algorithms; dynamic algorithms; squares; repetitions; runs