Finding Approximate Palindromes in Strings
Alexandre H.L. Porto, Valmir Carneiro Barbosa · 2002
We introduce a novel definition of approximate palindromes in strings, and provide an algorithm to find all maximal approximate palindromes in a string with up to k errors. Our definition is based on the usual edit operations of approximate pattern matching, and the algorithm we give, for a string of size n on a fixed alphabet, runs in O(k 2 n) time. We also discuss two implementationrelated improvements to the algorithm, and demonstrate their efficacy in practice by means of both experiments and an average-case analysis. Keywords: Approximate palindromes, string editing, approximate pattern matching. 1. Introduction Let S be a string of n characters from a fixed alphabet \\Sigma. For 1 i j n, let S[i] denote the ith character in S and S[i : : j] denote the substring of S whose first and last characters are S[i] and S[j], respectively. We let S R denote the string whose ith character is S[n \\Gamma i + 1], that is, S and S R are essentially the same string when read in oppos...