Lower Bound for String Matching on PRAM

Breslauer and Galil have shown that the string matching problem requires \Theta(d n p e + log log d1+p=ne 2p) rounds in the parallel comparison tree model with p comparisons in each round. In this note we show that the same lower bound even holds for the p-processor abstract Priority-CRCW PRAMs with bounded but arbitrary large memory. In this model one assumes that the internal computational power of the processors is unlimited, thus we lower bound the number of neccessary rounds of parallel read/write accesses to the shared memory. 1 Introduction Given two strings X[1 \Delta \Delta \Delta n], called the text, and Y[1 \Delta \Delta \Delta m], called the pattern, over an alphabet \Sigma. The string matching problem is to find all occurrences of the pattern in the text, that is, to find all i; 1 i n \Gamma m, such that X[i \Delta \Delta \Delta i + m \Gamma 1] = Y[1 \Delta \Delta \Delta m]. The problem of finding the period of a text Text[1 \Delta \Delta \Delta n] is to find the mi..