Our main result in this paper is a parallel algorithm for suffix-prefi
x- (s-p-) matching that has optimal speedup on a concurrent-read/concu
rrent-write parallel random-access machine (CRCW PRAM). Given a string
of length m, the algorithm runs in time O(log m) using m/log m proces
sors. This algorithm is important because we utilize s-p matching as a
fundamental building block to solve several pattern- and string-match
ing problems, such as the following: 1. string matching; 2. multitext/
multipattern string matching; 3. multidimensional pattern matching; 4.
pattern-occurrence detection; 5. on-line string matching. In particul
ar, our techniques and algorithms are the first to preserve optimal sp
eedup in the context of pattern matching in higher dimensions and are
the only known ones to do so for dimensions d > 2.