Efficient retrieval of approximate palindromes in a run-length encoded string
Journal
Theoretical Computer Science
Journal Volume
432
Pages
28-37
Date Issued
2012
Author(s)
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 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+mink,n) time with O(nlogn) preprocessing time, while the second algorithm achieves O(log 2n) query time, independent of k, after O( n2logn)-time preprocessing. © 2012 Elsevier B.V. All rights reserved.
Type
journal article