A lower bound for parallel string matching. (English) Zbl 0756.68048

Breslauer, Dany; Galil, Zvi

SIAM J. Comput. 21, No. 5, 856-862 (1992).

Summary: 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\dots m]\) in a text string \(T[1\dots 2m]\) in parallel using \(m\) comparisons in each round. The bound in within a constant factor of the fastest algorithm for this problem [D. Breslauer and Z. Galil, SIAM J. Comput. 19, 1051-1058 (1990; Zbl 0711.68057)] 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
\(\bullet\) \(\Theta\left({m\over p}\right)\) if \(p\leq{m\over \log\log m}\),
\(\bullet\;\Theta(\log\log m)\) if \({m\over\log\log m}\leq p\leq m\),
\(\bullet\;\Theta(\log\log_{2p/m}p)\) if \(m\leq p\leq m^ 2\),
\(\bullet\;\Theta(1)\) if \(p\geq m^ 2\),
or in short \(\Theta(\lceil{m\over p}\rceil+\log\log_{\lceil 1+p/m\rceil}2p)\).

MSC:

68Q25	Analysis of algorithms and problem complexity
68W10	Parallel algorithms in computer science
68W15	Distributed algorithms

Keywords:

period; lower bound; CRCW-PRAM; string matching

Citations:

Zbl 0711.68057