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

DOI10.7916/D8HH6T6R 10.1137/0219072; 10.7916/D8HH6T6RzbMath0711.68057MaRDI 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 algorithm; period; string

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68W10: Parallel algorithms in computer science

Related Items

On the lower bound for parallel string matching, Efficient string matching on packed texts, Optimal parallel algorithms for Prefix Matching, Optimal two-dimensional compressed matching, On the lower bound for parallel string matching, Optimal parallel algorithms for periods, palindromes and squares, Parallel detection of all palindromes in a string, Fast parallel string prefix-matching, A string-matching algorithm for the CREW PRAM, Optimal parallel two dimensional text searching on a CREW PRAM, Testing string superprimitivity in parallel, An efficient parallel algorithm for the single function coarsest partition problem, Sorting strings and constructing digital search trees in parallel, Parallel two dimensional witness computation, Finding all periods and initial palindromes of a string in parallel, Towards optimal packed string matching