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 …