Optimal parallel algorithms for prefix matching

Ramesh Hariharan, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    The Prefix Matching Problem is to determine, for each location in the text t, the longest prefix of a given pattern p which occurs beginning at that location. We present two work-optimal parallel algorithms for this problem. The first algorithm works for the case when the characters in p and t are drawn from an alphabet set of size polynomial in m + n, where m = |p| and n = |t|; it takes O(log m) time, O(m1+ε+n1+ε) space, and does O(m + n) work, for any ε>0. The second algorithm works for unbounded alphabet sets and takes O(log2m(log log m)3) time, O(m + n) space, and does O(m + n) work. These are the first known work-optimal algorithms for this problem.

    Original languageEnglish (US)
    Title of host publicationAutomata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings
    EditorsSerge Abiteboul, Eli Shamir
    PublisherSpringer Verlag
    Pages203-214
    Number of pages12
    ISBN (Print)9783540582014
    DOIs
    StatePublished - 1994
    EventProceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94 - Jerusalem, Isr
    Duration: Jul 1 1994Jul 1 1994

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume820 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    OtherProceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94
    CityJerusalem, Isr
    Period7/1/947/1/94

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Optimal parallel algorithms for prefix matching'. Together they form a unique fingerprint.

    Cite this