Fast Parallel String Prefix-Matching
Dany Breslauer · 1992
An 0(loglogm) time nlogm/loglogm-processor CRCW-PRAM algorithm for the string prefix-matching problem over a general alphabet is presented. The algorithm can also be used to compute the KMP failure function in 0(loglogm) time on mlogm/loglogm processors. These results improve on the running time of the best previous algorithm for both problems, which was 0 (log m), while preserving the same number of operations.