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.
Publisher Copyright:
© 1994, Springer Verlag. All rights reserved.
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 -