| z (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 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(log log m) time and does O(m 1 m 2) work, where m = maxfm 1; m 2 g. This yields a work optimal algorithm for 2D pattern matching which takes O(log log m) preprocessing time and O(1) text processing time. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||