Optimal Parallel Two Dimensional Text Searching on a CREW PRAM

AbstractWe present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes timeO(logm) on a CREW PRAM (wheremis the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in timeO(loglogm)