Optimal parallel two dimensional text searching on a CREW PRAM

DOI10.1006/inco.1998.2705zbMath0917.68049OpenAlexW1975363716MaRDI QIDQ1271473

Gary Benson, Amihood Amir, Martín Farach-Colton

Publication date: 25 March 1999

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1998.2705

zbMATH Keywords

analysis of algorithmsperiodstringpattern preprocessingblock compatibilityfast pattern matchingparallel algorithm for two dimensional text searchingtwo dimensional matching problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Pattern recognition, speech recognition (68T10) Distributed algorithms (68W15)

Related Items

Parallel two dimensional witness computation ⋮ Multidimensional period recovery ⋮ Lower bounds for the number of repetitions in 2D strings ⋮ Closest periodic vectors in \(L_p\) spaces ⋮ THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW ⋮ Some theoretical challenges in digital geometry: a perspective ⋮ Approximate periodicity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast string searching algorithm
• An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
• Optimal parallel pattern matching in strings
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Relations between Concurrent-Write Models of Parallel Computation
• Efficient string matching
• Fast Pattern Matching in Strings
• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Optimal Two-Dimensional Compressed Matching
• Two-Dimensional Periodicity in Rectangular Arrays