Swap Matching in Strings by Simulating Reactive Automata
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 automaton 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 conditions.
The resulting algorithms achieve
(n)
worst-case time complexity with patterns whose
length is comparable to the word-size of the target machine.
