A Constant Time Optimal Parallel Algorithm for Two-dimensional Pattern Matching

Maxime Crochemore, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, Wojciech Rytter

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size mh × mw in a text array of size nh × nw in the concurrentread-concurrent-write-parallel-random-access-machine (CRCW-PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(nh × nw) work, following preprocessing of the pattern. This improves the previous best bound of O(log log m) time with optimal work [A. Amir, G. Benson, and M. Farach, Proceedings 5th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1993, pp. 79-85], following preprocessing of the pattern, where m = max{mh, mw}. The preprocessing required by our algorithm (and that due to Amir, Benson, and Farach) can be accomplished in O(log log m) time and O(mh × mw) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].

    Original languageEnglish (US)
    Pages (from-to)668-681
    Number of pages14
    JournalSIAM Journal on Computing
    Volume27
    Issue number3
    DOIs
    StatePublished - 1998

    Keywords

    • Duelling
    • PRAM
    • Pattern matching
    • Periodicity
    • Two-dimensional
    • Witnesses

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'A Constant Time Optimal Parallel Algorithm for Two-dimensional Pattern Matching'. Together they form a unique fingerprint.

    Cite this