Parallel two dimensional witness computation

An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m 1×m 2 pattern is given. The algorithm takes O(loglogm) time and does O(m 1×m 2) work, where m=max{m 1, m 2}. This yields a work optimal algorithm for 2D pattern matching which takes O(loglogm) preprocessing time and O(1) text processing time.

Authors

• Richard Cole
• Zvi Galil
• Ramesh Hariharan
• S. Muthukrishnan
• Kunsoo Park

Keywords

No keywords are indexed for this paper.