Computing longest palindromic substring after single-character or block-wise edits

M Funakoshi, Y Nakashima, S Inenaga… - Theoretical Computer …, 2021 - Elsevier
Theoretical Computer Science, 2021Elsevier
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 …
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 ℓ.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果