Dany Breslauer, INRIA et Columbia Univ.

A Lower Bound for Parallel String Matching

We present an \$\Omega(\log\log m)\$ lower bound on the number of rounds necessary for finding occurrences of a pattern string~\$P[1\ldots m]\$ in a text string~\$T[1\ldots2m]\$ in parallel using~\$m\$ comparisons in each round. This is the first lower bound for this problem. The bound is within a constant factor of the fastest algorithm for this problem (Breslauer \& Galil) and also holds for an \$m\$-processor CRCW-PRAM in the case of a general alphabet. This is joint work with Zvi Galil.