Algorithms for Transposition Invariant String Matching
Veli Mäkinen, Gonzalo Navarro, Esko Ukkonen · 2003
Given strings A and B over an alphabet Sigma \\subset U, where U is some numerical universe closed under addition and subtraction, and a distance function d(A, B) that gives the score of the best (partial) matching of A and B, the transposition invariant distance is min t2U fd(A+t; B)g, where A+t = (a 1 +t)(a 2 +t) ... (a m +t). We study the problem of computing the transposition invariant distance for various distance (and similarity) functions d, including Hamming distance, longest common subsequence (LCS), edit distance, and their versions where the exact matching condition is replaced by an approximate one. For all these problems we give algorithms whose time complexities are close to the known upper bounds without transposition invariance, and for some we achieve these upper bounds. In particular, we show how sparse dynamic programming can be used to solve transposition invariant problems.