TY - GEN

T1 - Optimal parallel algorithms for prefix matching

AU - Hariharan, Ramesh

AU - Muthukrishnan, S.

N1 - Funding Information:
*The work of this author was supported in part by NSF grants CCR-8902221 and CCR-8906949. tThe work of this author was supported in part by NSF/DARPA grant CCR-89-06949 and NSF grant CCR-91-03953.
Funding Information:
The work of this author was supported in part by NSF grants CCR-8902221 and CCR-8906949. The work of this author was supported in part by NSF/DARPA grant CCR-89-06949 and NSF grant CCR-91-03953.

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=21344498092&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21344498092&partnerID=8YFLogxK

U2 - 10.1007/3-540-58201-0_69

DO - 10.1007/3-540-58201-0_69

M3 - Conference contribution

AN - SCOPUS:21344498092

SN - 9783540582014

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 203

EP - 214

BT - Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings

A2 - Abiteboul, Serge

A2 - Shamir, Eli

PB - Springer Verlag

T2 - Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94

Y2 - 1 July 1994 through 1 July 1994

ER -