Crochemore, Maxime ; Gasieniec, Leszek ; Hariharan, Ramesh ; Muthukrishnan, S. ; Rytte, Wojciech (1998) A constant time optimal parallel algorithm for two-dimensional pattern matching SIAM Journal on Computing, 27 (3). pp. 669-681. ISSN 0097-5397
Full text not available from this repository.
Official URL: http://epubs.siam.org/doi/abs/10.1137/S00975397952...
Related URL: http://dx.doi.org/10.1137/S0097539795280068
Abstract
We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size mh x mw in a text array of size nh x nw 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(nh x nw) 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, 1993, pp. 79--85], following preprocessing of the pattern, where m = max{mh, mw}.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Society for Industrial and Applied Mathematics. |
| ID Code: | 102349 |
| Deposited On: | 09 Mar 2018 11:24 |
| Last Modified: | 09 Mar 2018 11:24 |
Repository Staff Only: item control page
