Maxime Crochemore, Gad M. Landau, et al.
SODA 2002
Conference paper
Optimal parallel suffix-prefix matching algorithm and applications
Abstract
Our main result in this paper is a parallel algorithm for suffiz-prefix matching that has optimal speedup on a CRCW PRAM. It runs in time O(logn) using n/log n processors. This algorithm is important because we utihze suffix-prefix matching as a fundamental building block to solve several pattern and string matching problems such as: 1. String Matching, 2. Multi-pattern string matching, 3. Multidimensional Pattern Matching, 4. Pattern Occurrence Detection, 5. Incremental String Matching.
Related
Conference paper
On communication latency in PRAM computations
Alok Aggarwal, Ashok K. Chandra, et al.
SPAA 1989
Revital Eres, Gad M. Landau, et al.
Journal of Computational Biology
Gad M. Landau, Baruch Schieber, et al.
Information Processing Letters