Approximate Swapped Matching

A. Amir and M. Lewenstein and E. Porat

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


The Pattern Matching with Swaps problem is that of finding all locations in text T that equal a pattern P where adjacent symbols may be swapped, but no symbol may be swapped more than once. Recently, some efficient algorithms were developed for this problem. Their time complexity is better than the best known algorithms for pattern matching with mismatches. However, the Approximate Pattern Matching with Swaps problem (where we output, for every text location where there is a swap match, the number of swaps) was not known to be solved faster than the pattern matching with mismatches problem. The fastest known method to-date is that of counting mismatches and dividing by two. In this paper we show an algorithm that counts the number of swaps at every location where there is a swapped matching in time O(n log m log s), where s= min(m,|A|), and A is the alphabet. Consequently, the total time for solving the approximate pattern matching with swaps problem is faster than the best known algorithm for pattern matching with mismatches.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems