2026-07-20T05:35:47Z https://drops.dagstuhl.de/oai

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

Shortest Cover After Edit Mitani, Kazuki Mieno, Takuya Seto, Kazuhisa Horiyama, Takashi string algorithm border cover quasi-periodicity dynamic string This paper investigates the (quasi-)periodicity of a string when the string is edited. A string C is called a cover (as known as a quasi-period) of a string T if each character of T lies within some occurrence of C. By definition, a cover of T must be a border of T; that is, it occurs both as a prefix and as a suffix of T. In this paper, we focus on the changes in the longest border and the shortest cover of a string when the string is edited only once. We propose a data structure of size O(n) that computes the longest border and the shortest cover of the string in O(𝓁 log n) time after an edit operation (either insertion, deletion, or substitution of some string) is applied to the input string T of length n, where 𝓁 is the length of the string being inserted or substituted. The data structure can be constructed in O(n) time given string T. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kazuki Mitani and Takuya Mieno and Kazuhisa Seto and Takashi Horiyama 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.24 urn:nbn:de:0030-drops-201345 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.24 eng https://creativecommons.org/licenses/by/4.0/legalcode