A constant time optimal parallel algorithm for two-dimensional pattern matching. (English) Zbl 0912.68067

Summary: We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size \(m_h \times m_{w}\) in a text array of size \(n_h \times 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 \times 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, 79-85 (1993)], 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 \times m_w)\) work [M. Crochemore, L. Gasieniec, Z. Galil, K.Park and W. Rytter, Constant time deterministic sample computation and its applications, manuscript (1993); R. Cole, Z. Galil, R. Hariharan, S. Muthukrishnan and K. Park, Optimal parallel two-dimensional witness computation, manuscript (1993)].


68W15 Distributed algorithms
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI