
Summary: The author presents a simple algorithm for solving the multipattern matching problem with optimal speedup. The best-known deterministic parallel algorithm for this problem also provides optimal speedup, but relies crucially on a sophisticated construction of an automaton. Since then, Rabin has introduced a simple and elegant parallel algorithm [\textit{M. Rabin}, in Sequences '91: Methods in Communication, Security, and Computer Science (1993)]. This is a Monte Carlo algorithm based on finger-print functions and it, too, has optimal speedup. His algorithm simultaneously achieves the goals of optimal speedup of the deterministic algorithm, as well as the simplicity of the randomized Monte Carlo design cited above. His algorithm presented here can also be extended to solve the multidimensional pattern-matching problem, also with optimal speedup. Interestingly, the sequential version of the algorithm derived by slowing down our parallel design yields a new and simple (linear-time) algorithm for string matching. It is distinguished by its lack of dependence on failure-functions and its related automata-theoretic variants, periodicities, or special data structures, but essentially uses a carefully constructed divide-and-conquer approach. This approach is systematized by us into the shrink-and-spawn technique, with a range of applications in parallel string and pattern matching in a paper that appears in \textit{S. Muthukrishnan} and \textit{K. Palem} [in ``Proceedings 5th ACM Symp. on Parallel Algorithms and Architectures, 69-78 (1993)].
multipattern matching, Parallel algorithms in computer science
multipattern matching, Parallel algorithms in computer science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
