Domenico Cantone and Simone Faro
A Space Efficient Bit-Parallel Algorithm for the Multiple String Matching Problem
Finite (nondeterministic) automata are very useful building blocks in
the field of string matching. This is particularly true in the case
of multiple pattern matching, where the use of factor-based automata
can reduce substantially the number of computational steps when the
patterns have large common factors.
Direct simulation of nondeterministic automata can be performed very efficiently using the bit-parallelism technique, though this is not necessarily true for factor-based automata.
In this paper we present an algorithm for the multiple string matching problem, based on the bit-parallel simulation of nondeterministic factor-based automata which satisfy a particular ordering condition. We also show how to enforce such condition by suitably modifying a minimal initial automaton, through equivalence preserving transformations. The resulting automaton turns out to be smaller than the corresponding maximal automata used by existing bit-parallel algorithms, as they do not take any advantage of common factors in patterns.