About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SPAA 1989
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.