A Simpler Bit-parallel Algorithm for Swap Matching.
Václav Blažej, Ondřej Suchý, Tomáš Valla · arXiv (Cornell University) · 2016
The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions. We point out a fatal flaw in the algorithm proposed by Ahmed et al. [The swap matching problem revisited, Theor. Comp. Sci. 2014], which we describe in detail. Furthermore we devise a new swap pattern matching algorithm which is based on the same graph theoretical model as the algorithm by Ahmed et al. (thus still not based on FFT) and we prove its correctness. We also show that an approach using deterministic finite automata cannot achieve similarly efficient algorithms.