An 0(loglogm) time nlogm/loglogm-processor CRCW-PRAM algorithm for the stringprefix-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.
展开▼
