A LOWER BOUND FOR PARALLEL STRING MATCHING

This paper presents an OMEGA(log log m) lower bound on the number of rounds necessary for finding occurrences of a pattern string P[1..m] in a text string T[1..2m] in parallel using m comparisons in each The bound is within a constant factor of the fastest algorithm for this problem [D. Breslauer and Z. Galil, SLAM J. Comput., 19 (1990), pp. 1051-1058] and also holds for an m-processor CRCW-PRAM in the case of a general alphabet. Consequently, the paper derives the parallel complexity of the string matching problem using p processors for general alphabets, which is THETA(m/p) if p less-than-or-equal-to m/log log m, THETA(log log m) if m/log log m less-than-or-equal-to p less-than-or-equal-to m, THETA (log log2p/m p) if m less-than-or-equal-to p less-than-or-equal-to m2, THETA(1) if p greater-than-or-equal-to m2, or in short THETA([m/p] + log log[1+p/m] 2p).