2026-07-20T05:23:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8697 2024-03-06T10:43:01Z ddc:004 open_access

Longest substring palindrome after edit Funakoshi, Mitsuru Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki maximal palindromes edit operations periodicity suffix trees It is known that the length of the longest substring palindromes (LSPals) of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(log (min {sigma, log n })) time after single character substitution, insertion, or deletion, where sigma denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(l + log n) time, after an existing substring in T is replaced by a string of arbitrary length l. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mitsuru Funakoshi and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.12 urn:nbn:de:0030-drops-86977 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.12 eng https://creativecommons.org/licenses/by/3.0/legalcode