TY - JOUR
T1 - Optimal Parallel Two Dimensional Text Searching on a CREW PRAM
AU - Amir, Amihood
AU - Benson, Gary
AU - Farach-Colton, Martin
N1 - Funding Information:
* Partially supported by NSF Grant CCR-96-1070 and the Israel Ministry of Science and the Arts Grants 6297 and 8560. -Partially supported by NSF Grant CCR-96-23532. Supported by DIMACS under NSF Contract STC-88-09648.
PY - 1998/7/10
Y1 - 1998/7/10
N2 - We present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(log m) on a CREW PRAM (where m is the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(log log m).
AB - We present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(log m) on a CREW PRAM (where m is the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(log log m).
KW - Analysis of algorithms
KW - Multidimensional matching
KW - Parallel algorithms
KW - Period
KW - String
UR - https://www.scopus.com/pages/publications/0347611276
U2 - 10.1006/inco.1998.2705
DO - 10.1006/inco.1998.2705
M3 - Article
AN - SCOPUS:0347611276
SN - 0890-5401
VL - 144
SP - 1
EP - 17
JO - Information and Computation
JF - Information and Computation
IS - 1
ER -