Optimal parallel two dimensional text searching on a CREW PRAM
From MaRDI portal
Publication:1271473
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
analysis of algorithmsperiodstringpattern preprocessingblock compatibilityfast pattern matchingparallel algorithm for two dimensional text searchingtwo dimensional matching problem
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