SIAM Journal on Computing · 1990 · 72 citations · 9 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisData ParallelismParallel Algorithm DesignParallel Data StructuresParallel SearchingString AlgorithmsComplexity Of String AlgorithmsParallel Algorithm AnalysisParallel Algorithm ComplexityParallel Matching AlgorithmsParallel String MatchingString SearchString Searching
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].
9
Fast Pattern Matching in Strings
Donald E. Knuth, James H. Morris, Vaughan Pratt · SIAM Journal on Computing · 1977 · 2.9K citations
A fast string searching algorithm
Robert S. Boyer, J Strother Moore · Communications of the ACM · 1977 · 2.3K citations · Full text
The Parallel Evaluation of General Arithmetic Expressions
Richard P. Brent · Journal of the ACM · 1974 · 818 citations · Full text
Parallelism in Comparison Problems
Leslie G. Valiant · SIAM Journal on Computing · 1975 · 401 citations