A Constant Time Optimal Parallel Algorithm for Two-dimensional Pattern Matching

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

doi:10.1137/S0097539795280068

A Constant Time Optimal Parallel Algorithm for Two-dimensional Pattern Matching

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

Research output: Contribution to journal › Article › peer-review

Abstract

We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size m_h × m_w in a text array of size n_h × n_w in the concurrentread-concurrent-write-parallel-random-access-machine (CRCW-PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(n_h × 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, 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(log log m) time and O(m_h × m_w) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].

Original language	English (US)
Pages (from-to)	668-681
Number of pages	14
Journal	SIAM Journal on Computing
Volume	27
Issue number	3
DOIs	https://doi.org/10.1137/S0097539795280068
State	Published - 1998

Keywords

Duelling
PRAM
Pattern matching
Periodicity
Two-dimensional
Witnesses

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S0097539795280068

Cite this

@article{e4245bac1fb44fa3b190205bb087771d,

title = "A Constant Time Optimal Parallel Algorithm for Two-dimensional Pattern Matching",

abstract = "We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size mh × mw in a text array of size nh × nw in the concurrentread-concurrent-write-parallel-random-access-machine (CRCW-PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(nh × 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}. 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(mh × mw) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].",

keywords = "Duelling, PRAM, Pattern matching, Periodicity, Two-dimensional, Witnesses",

author = "Maxime Crochemore and Leszek Gasieniec and Ramesh Hariharan and S. Muthukrishnan and Wojciech Rytter",

year = "1998",

doi = "10.1137/S0097539795280068",

language = "English (US)",

volume = "27",

pages = "668--681",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - A Constant Time Optimal Parallel Algorithm for Two-dimensional Pattern Matching

AU - Crochemore, Maxime

AU - Gasieniec, Leszek

AU - Hariharan, Ramesh

AU - Muthukrishnan, S.

AU - Rytter, Wojciech

PY - 1998

Y1 - 1998

N2 - We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size mh × mw in a text array of size nh × nw in the concurrentread-concurrent-write-parallel-random-access-machine (CRCW-PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(nh × 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}. 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(mh × mw) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].

AB - We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size mh × mw in a text array of size nh × nw in the concurrentread-concurrent-write-parallel-random-access-machine (CRCW-PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(nh × 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}. 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(mh × mw) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].

KW - Duelling

KW - PRAM

KW - Pattern matching

KW - Periodicity

KW - Two-dimensional

KW - Witnesses

UR - http://www.scopus.com/inward/record.url?scp=0346984925&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346984925&partnerID=8YFLogxK

U2 - 10.1137/S0097539795280068

DO - 10.1137/S0097539795280068

M3 - Article

AN - SCOPUS:0346984925

SN - 0097-5397

VL - 27

SP - 668

EP - 681

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

A Constant Time Optimal Parallel Algorithm for Two-dimensional Pattern Matching

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this