Optimal parallel algorithms for string matching

DOI10.1016/S0019-9958(85)80031-0MaRDI QIDQ3716298zbMATH OpenFDO

Authors Zvi Galil

Publication date 1985

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(85)80031-0

zbMATH Keywords

parallel computationPRAMWRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3911754
• Optimal parallel pattern matching in strings
• An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
• scientific article; zbMATH DE number 4205980
• A Lower Bound for Parallel String Matching

Cited in

(41)

• Fast string matching with k differences
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• Optimal parallel detection of squares in strings
• Efficient CRCW-PRAM algorithms for universal substring searching
• Parallel finding all initial palindromes and periods of a string on reconfigurable meshes
• Alphabet-independent optimal parallel search for three-dimensional patterns
• On two-dimensional pattern matching by optimal parallel algorithms
• Finding approximate palindromes in strings
• Finding all periods and initial palindromes of a string in parallel
• Multidimensional period recovery
• Fast parallel and serial multidimensional approximate array matching
• Approximate periodicity
• Towards optimal packed string matching
• Closest periodic vectors in \(L_p\) spaces
• A parallel multistart algorithm for the closest string problem
• Algorithms in the ultra-wide word model
• Real-time streaming string-matching
• scientific article; zbMATH DE number 4205980 (Why is no real title available?)
• scientific article; zbMATH DE number 3911754 (Why is no real title available?)
• Optimal parallel pattern matching in strings
• A Lower Bound for Parallel String Matching
• scientific article; zbMATH DE number 1263250 (Why is no real title available?)
• Fast parallel Lyndon factorization with applications
• On the lower bound for parallel string matching
• Efficient string matching on packed texts
• A constant-time optimal parallel string-matching algorithm
• Constant-Time Randomized Parallel String Matching
• scientific article; zbMATH DE number 1948479 (Why is no real title available?)
• Optimal parallel algorithms for Prefix Matching
• On the lower bound for parallel string matching
• Forty Years of Text Indexing
• On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
• Parallel String Matching
• Finding the cyclic covers of a string
• Parallel detection of all palindromes in a string
• Fast parallel string prefix-matching
• A string-matching algorithm for the CREW PRAM
• Finding the cyclic covers of a string
• String problems in the congested clique model
• String problems in the congested clique model
• Parallel tree pattern matching

This page was built for publication: Optimal parallel algorithms for string matching

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