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

AbstractIn this paper, we study the palindrome retrieval problem with the input string compressed into run-length encoded form. Given a run-length encoded string rle(T), we show how to preprocess rle(T) 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 rle(T) 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