1. Efficient retrieval of approximate palindromes in a run-length encoded string
- Author
-
Chen, Kuan-Yu, Hsu, Ping-Hui, and Chao, Kun-Mao
- Subjects
- *
PALINDROMES , *INFORMATION retrieval software , *ELECTRONIC data processing , *COMPUTER input design , *MATCHING theory , *QUERY (Information retrieval system) , *ALGORITHMS - Abstract
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 denote the number of runs of and let denote the number of mismatches. The first algorithm, devised for small , identifies the desired palindrome in time with preprocessing time, while the second algorithm achieves query time, independent of , after -time preprocessing. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF