An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
Dany Breslauer, Zvi Galil · SIAM Journal on Computing · 1990
An optimal $O(\log \log n)$ time parallel algorithm for string matching on CROW-PRAM is presented. It improves previous results of Galil [Inform, and Control, 67 (1985), pp. 144–157] and Vishkin [Inform, and Control, 67 (1985), pp. 91–113].