Optimal parallel two dimensional text searching on a CREW PRAM (Q1271473)

In this paper, the efficient parallel algorithm for two dimensional pattern matching over a general alphabet is presented. The text processing phase is optimal in that its work is linear and its running time is optimal; i.e., it matches the lower bound \(O(\log m)\) for CREW PRAMs, where \(m\) is the length of the longest dimension of the pattern. Furthermore, it makes no assumptions about the character alphabet. On a CRCW PRAM, the algorithm runs optimally in time \(O(\log \log m),\) thus matching the lower bound for string matching on a PRAM without concurrent writes. The design of such an algorithm was posed as an open problem by \textit{U. Vishkin} [Optimal parallel pattern matching in strings, \textit{in} ``Proceeding 12th ICALP,'' 91-113 (1985)].