Simple Optimal Parallel Multiple Pattern Matching

S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review


    In this paper, we present 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 (M. Rabin, in "Sequences '91: Methods in Communication, Security, and Computer Science," Springer-Verlag, New York/Berlin, 1993). This is a Monte-carlo algorithm based on finger-print functions and it, too, has optimal speedup. Our 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. Our 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 S. Muthukrishnan and K. Palem (in "Proceedings 5th ACM Symp. on Parallel Algorithms and Architectures, 1993," pp. 69-78).

    Original languageEnglish (US)
    Pages (from-to)1-13
    Number of pages13
    JournalJournal of Algorithms
    Issue number1
    StatePublished - Jan 2000

    ASJC Scopus subject areas

    • Control and Optimization
    • Computational Mathematics
    • Computational Theory and Mathematics


    Dive into the research topics of 'Simple Optimal Parallel Multiple Pattern Matching'. Together they form a unique fingerprint.

    Cite this