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.
