A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching
Maxime Crochemore, Leszek Antoni Gąsieniec, Ramesh Hariharan, Subramanian Muthukrishnan, Wojciech Rytter · SIAM Journal on Computing · 1998
We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size m h x m w in a text array of size n h x n w in the concurrent-read-concurrent-write--parallel-random-access-machine (CRCW--PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(n h x n w ) work, following preprocessing of the pattern. This improves the previous best bound of O(log log m ) time with optimal work [A. Amir, G. Benson, and M. Farach, Proceedings 5th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1993, pp. 79--85], following preprocessing of the pattern, where m=max{m h , m w }. The preprocessing required by our algorithm (and that due to Amir, Benson, and Farach) can be accomplished in O(log log m) time and O(m h x m w ) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].