An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
From MaRDI portal
Publication:3495651
DOI10.1137/0219072zbMath0711.68057OpenAlexW2086273045MaRDI QIDQ3495651
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0219072
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10)
Related Items
An efficient parallel algorithm for the single function coarsest partition problem ⋮ Parallel two dimensional witness computation ⋮ Finding all periods and initial palindromes of a string in parallel ⋮ Sorting strings and constructing digital search trees in parallel ⋮ On the lower bound for parallel string matching ⋮ On the lower bound for parallel string matching ⋮ Towards optimal packed string matching ⋮ Efficient string matching on packed texts ⋮ Optimal parallel algorithms for Prefix Matching ⋮ Optimal two-dimensional compressed matching ⋮ Parallel detection of all palindromes in a string ⋮ Fast parallel string prefix-matching ⋮ A string-matching algorithm for the CREW PRAM ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Optimal parallel two dimensional text searching on a CREW PRAM ⋮ Testing string superprimitivity in parallel
