Constant-Time Randomized Parallel String Matching

DOI10.1137/S009753979528007XMaRDI QIDQ4376173zbMATH OpenOpenAlexFDO

Authors Maxime Crochemore, Zvi Galil, Leszek Gąsieniec, Kunsoo Park, Wojciech Rytter

Publication date 10 February 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s009753979528007x

zbMATH Keywords

deterministic samplesparallel string matchingrandomized algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Distributed algorithms (68W15)

Recommendations

• A constant-time optimal parallel string-matching algorithm
• Parallel String Matching Algorithms
• scientific article; zbMATH DE number 826050
• An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
• Optimal parallel algorithms for string matching
• scientific article; zbMATH DE number 3911754
• Optimal parallel pattern matching in strings
• scientific article; zbMATH DE number 710402
• Fast parallel and serial approximate string matching

Cited in

(15)

• Boolean circuit programming: A new paradigm to design parallel algorithms
• Efficient CRCW-PRAM algorithms for universal substring searching
• Detecting false matches in string-matching algorithms
• Parallel two dimensional witness computation
• Towards optimal packed string matching
• Fast string matching in stationary ergodic sources
• Constant-time word-size string matching
• Efficient randomized pattern-matching algorithms
• A Lower Bound for Parallel String Matching
• Faster Parallel String Matching via Larger Deterministic Samples
• Efficient string matching on packed texts
• A constant-time optimal parallel string-matching algorithm
• On the lower bound for parallel string matching
• scientific article; zbMATH DE number 826061 (Why is no real title available?)
• String matching in O( n+ m) quantum time

This page was built for publication: Constant-Time Randomized Parallel String Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376173)