Yet another efficient algorithm for the Swap Matching problem
Pritom Ahmed, A. S. M. Sohidull Islam, M. Sohel Rahman · 2012
In this paper, we revisit the much studied problem of Pattern matching with Swaps (Swap Matching problem, for short). We study the graph theoretic model proposed by [8] and using the model, devise an efficient algorithm to solve the swap matching problem. The resulting algorithm is an adaptation of the classic shift-and algorithm. For patterns having length similar to the word-size of the target machine, the algorithm runs in O(n) time, where n and m are the length of the text and the pattern respectively.