文章基本信息

标题：Faster Queries for Longest Substring Palindrome After Block Edit
本地全文：下载
作者：Mitsuru Funakoshi ; Yuto Nakashima ; Shunsuke Inenaga 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：128
页码：1-13
DOI：10.4230/LIPIcs.CPM.2019.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. Manacher [J. ACM 1975] proposed a seminal algorithm that computes the longest substring palindromes (LSPals) of a given string in O(n) time, where n is the length of the string. 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(l + log log n) time, after a substring in T is replaced by a string of arbitrary length l. This outperforms the query algorithm proposed in our previous work [CPM 2018] that uses O(l + log n) time for each query.
关键词：palindromes; string algorithm; periodicity