Efficient retrieval of approximate palindromes in a run-length encoded string

In this paper, we study the palindrome retrieval problem with the input string compressed into run-length encoded form. Given a run-length encoded string , we show how to preprocess  to support subsequent queries of the longest palindrome centered at any specified position and having any specified number of mismatches between its arms. We present two algorithms for the problem, both taking time and space polynomial in the compressed string size. Let n denote the number of runs of  and let k denote the number of mismatches. The first algorithm, devised for small k, identifies the desired palindrome in O(logn+min{k,n}) time with O(nlogn) preprocessing time, while the second algorithm achieves O(log2n) query time, independent of k, after O(n2logn)-time preprocessing.