Optimal Parallel Two Dimensional Text Searching on a CREW PRAM

Amihood Amir, Gary Benson, Martin Farach-Colton

    Research output: Contribution to journalArticlepeer-review


    We present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(log m) on a CREW PRAM (where m is the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(log log m).

    Original languageEnglish (US)
    Pages (from-to)1-17
    Number of pages17
    JournalInformation and Computation
    Issue number1
    StatePublished - Jul 10 1998


    • Analysis of algorithms
    • Multidimensional matching
    • Parallel algorithms
    • Period
    • String

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Information Systems
    • Computer Science Applications
    • Computational Theory and Mathematics


    Dive into the research topics of 'Optimal Parallel Two Dimensional Text Searching on a CREW PRAM'. Together they form a unique fingerprint.

    Cite this