Simple optimal parallel multiple pattern matching

In this paper, we present a simple algorithm for solving the multipattern m atching problem, with optimal speedup. The best-known deterministic paralle l algorithm for this problem also provides optimal speedup, but relies cruc ially on a sophisticated construction of an automaton. Since then, Rabin ha s introduced a simple and elegant parallel algorithm (M. Rabin, in Sequence s '91: Methods in Communication, Security, and Computer Science," Springer- Verlag, New York/Berlin, 1993). This is a Monte-carlo algorithm based on fi nger-print functions and it, too, has optimal speedup. Our algorithm simult aneously achieves the goals of optimal speedup of the deterministic algorit hm, as well as the simplicity of the randomized Monte-carlo design cited ab ove. Our algorithm presented here can also be extended to solve the multidi mensional pattern-matching problem, also with optimal speedup. Interestingl y, the sequential version of the algorithm derived by slowing down our para llel design yields a new and simple (linear-time) algorithm for string matc hing. It is distinguished by its lack of dependence on failure-functions an d its related automata-theoretic variants, periodicities, or special data s tructures, but essentially uses a carefully constructed divide-and-conquer approach. This approach is systematized by us into the shrink-and-spawn tec hnique, with a range of applications in parallel string and pattern matchin g in a paper that appears in S. Muthukrishnan and K. Palem (in "Proceedings 5th ACM Symp. on Parallel Algorithms and Architectures, 1993," pp. 69-78). (C) 2000 Academic Press.