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.