On a compact encoding of the swap automaton

• New algorithm for the Pattern Matching with Swaps problem.
• Method based on finite automata and word-level parallelism.
• We improve over the existing bound in the word-RAM model.

Given a string P of length m over an alphabet Σ of size σ, a swapped version of P is a string derived from P   by a series of local swaps, i.e., swaps of adjacent symbols, such that each symbol can participate in at most one swap. We present a theoretical analysis of the nondeterministic finite automaton for the language ⋃P′∈ΠPΣ⁎P′⋃P′∈ΠPΣ⁎P′ (swap automaton, for short), where ΠPΠP is the set of swapped versions of P  . Our study is based on the bit-parallel simulation of the same automaton due to Fredriksson, and reveals an interesting combinatorial property that links the automaton to the one for the language Σ⁎PΣ⁎P. By exploiting this property and the method presented by Cantone et al. (2012), we obtain a bit-parallel encoding of the swap automaton which takes O(σ2⌈k/w⌉)O(σ2⌈k/w⌉) space and allows one to simulate the automaton on a string of length n   in time O(n⌈k/w⌉)O(n⌈k/w⌉), where ⌈m/σ⌉⩽k⩽m⌈m/σ⌉⩽k⩽m is the size of a specific factorization of P defined by Cantone et al. (2012) and w is the word size in bits.