Computing longest palindromic substring after single-character or block-wise edits
Computing longest palindromic substring after single-character or block-wise edits
复制标题
在单字符或按块编辑后计算最长的回文子串
DOI：
10.1016/j.tcs.2021.01.014
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Takeda Masayuki
中科院分区：
文献类型：
--
作者：
Funakoshi Mitsuru;Nakashima Yuto;Inenaga Shunsuke;Bannai Hideo;Takeda Masayuki
回文是字符串中的重要对象，已经从组合、算法和生物信息学的角度进行了广泛的研究。众所周知，长度为n的给定字符串T的最长回文子串(LPS)的长度可以通过Manacher算法[12]在O(N)时间内计算。在这篇文章中，我们考虑了在字符串编辑后寻找LPS的问题。提出了一种使用O(N)时间和空间进行预处理的算法，并在单个字符替换、插入或删除后在O(LOG(min{σ，LOGn}))时间内回答LPS的长度，其中σ表示出现在T中的不同字符的个数。我们还提出了一种算法，该算法使用O(N)时间和空间进行预处理，在T中的现有子串被任意长度的字符串替换后，在O(ℓ+LOGLOGn)时间内回答LPS的长度。
Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of the longest palindromic substrings (LPSs) of a given string T of length n can be computed in O (n) time by Manacher's algorithm [12]. In this paper, we consider the problem of finding the LPS after the string is edited. We present an algorithm that uses O (n) time and space for preprocessing, and answers the length of the LPSs in O (log(min{σ, log n})) time after a single character substitution, insertion, or deletion, where σ 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 LPSs in O (ℓ+ log log n) time, after an existing substring in T is replaced by a string of arbitrary length ℓ.