The Prague Stringology Conference 2005
Domenico Cantone and Simone Faro
A Space Efficient Bit-Parallel Algorithm for the Multiple String Matching Problem
| Abstract: |
|
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. |
| Download paper: |  |
 |
| PostScript |