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

Crochemore, Maxime; Gasieniec, Leszek; Hariharan, Ramesh; Muthukrishnan, S.; Rytter, Wojciech

SIAM J. Comput. 27, No. 3, 668-681 (1998).

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)].

MSC:

68W15	Distributed algorithms
68Q25	Analysis of algorithms and problem complexity

Keywords:

pattern matching; PRAM; two-dimensional; witnesses; duelling; periodicity