Fast parallel string prefix-matching

An O(log log m) time n log m log log m -processor CRCW-PRAM algorithm for the string prefix-matching problem over general alphabets is presented. The algorithm can also be used to compute the KMP failure function 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 problems, which was O(log m), while preserving the same number of operations.

Authors

• Dany Breslauer

Keywords

No keywords are indexed for this paper.