Swap Matching in Strings by Simulating Reactive Automata.
Simone Faro · 2013
Abstract. The pattern matching problem with swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In this paper we introduce a new theoretical approach to the problem based on a reactive au-tomaton modeled after the pattern, and provide two efficient non standard simulations of the automaton, based on bit-parallelism. The first simulation can be implemented by at least 7 bitwise operations, while the second one involves only 2 bitwise operations to simulate the automaton behavior, when the input pattern satisfies particular condi-tions. The resulting algorithms achieve O(n) worst-case time complexity with patterns whose length is comparable to the word-size of the target machine.