Search

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]

Abstract: Given a string x and a language L, the Hamming distance of x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a language is analogously defined. First, we prove that there is a language in such that both Hamming and edit distance to this language are hard to approximate; they cannot be approximated with factor , for any , unless (n denotes the length of the input string). Second, we show the parameterized intractability of computing the Hamming distance. We prove that for every there exists a language in for which computing the Hamming distance is -hard. Moreover, there is a language in for which computing the Hamming distance is -hard. Then we show that the problems of computing the Hamming distance and of computing the edit distance are in some sense equivalent by presenting approximation ratio preserving reductions from the former to the latter and vice versa. Finally, we define to be the class of languages to which the Hamming distance can efficiently, i.e.in polynomial time, be computed. We show some properties of the class . On the other hand, we give evidence that a characterization in terms of automata or formal languages might be difficult. [Copyright &y& Elsevier]