Article ID Journal Published Year Pages File Type
434857 Theoretical Computer Science 2012 10 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics