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.