A CONSTANT-TIME OPTIMAL PARALLEL ALGORITHM FOR 2-DIMENSIONAL PATTERN-MATCHING

We give an alphabet-independent deterministic parallel algorithm for f inding all occurrences of a pattern array of size m(h) x m(w) in a tex t array of size n(h) x n(w) in the ad-concurrent-write-parallel-random -access-machine (CRCW-PRAM) model. Our algorithm runs in O(1) time per forming optimal, that is, O(n(h) x n(w)) work, following preprocessing of the pattern. This improves the previous best bound of O(loglogm) t ime 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(l oglogm) time and O(m(h) x m(w)) work [M. Crochemore et al., manuscript , 1993], [R. Cole et al., manuscript, 1993].