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.