An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm

DOI10.1137/0219072zbMath0711.68057OpenAlexW2086273045MaRDI QIDQ3495651

Dany Breslauer, Zvi Galil

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

zbMATH Keywords

parallel algorithmperiodstring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10)

Related Items (16)

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

This page was built for publication: An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm