Optimal parallel two dimensional text searching on a CREW PRAM (Q1271473): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Martín Farach-Colton / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Nikolay Yakovlevich Tikhonenko / rank | |||
Normal rank |
Revision as of 20:07, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal parallel two dimensional text searching on a CREW PRAM |
scientific article |
Statements
Optimal parallel two dimensional text searching on a CREW PRAM (English)
0 references
25 March 1999
0 references
In this paper, the efficient parallel algorithm for two dimensional pattern matching over a general alphabet is presented. The text processing phase is optimal in that its work is linear and its running time is optimal; i.e., it matches the lower bound \(O(\log m)\) for CREW PRAMs, where \(m\) is the length of the longest dimension of the pattern. Furthermore, it makes no assumptions about the character alphabet. On a CRCW PRAM, the algorithm runs optimally in time \(O(\log \log m),\) thus matching the lower bound for string matching on a PRAM without concurrent writes. The design of such an algorithm was posed as an open problem by \textit{U. Vishkin} [Optimal parallel pattern matching in strings, \textit{in} ``Proceeding 12th ICALP,'' 91-113 (1985)].
0 references
parallel algorithm for two dimensional text searching
0 references
analysis of algorithms
0 references
two dimensional matching problem
0 references
period
0 references
string
0 references
pattern preprocessing
0 references
block compatibility
0 references
fast pattern matching
0 references