FAST PARALLEL STRING PREFIX-MATCHING

Authors
Citation
D. Breslauer, FAST PARALLEL STRING PREFIX-MATCHING, Theoretical computer science, 137(2), 1995, pp. 269-278
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
ISSN journal
03043975
Volume
137
Issue
2
Year of publication
1995
Pages
269 - 278
Database
ISI
SICI code
0304-3975(1995)137:2<269:FPSP>2.0.ZU;2-J
Abstract
An O(log log m) time n log m/log log m-processor CRCW-PRAM algorithm f or the string prefix-matching problem over general alphabets is presen ted. The algorithm can also be used to compute the KMP failure functio n in O(log log m) time on m log m/log log m processors. These results improve on the running time of the best previous algorithm for both pr oblems, which was O(log m), while preserving the same number of operat ions.