What do you think?
Rate this book
Optimal Parallel Pattern Matching in Strings
Excerpt from Optimal Parallel Pattern Matching in Strings
There are two known linear time serial algorithms for this extensively studied problem, due to [em  77] and [kmp Recall that every parallel linear algorithms is, in particular, a linear time serial algorithm. The present result is stronger than theirs in the sense that it gives a parallel linear algorithm while theirs serial algorithms do not seem to imply satisfactory parallel linear algorithms. Moreover, our algorithm is not more complicated than theirs. Some parts of it (particularly, the analysis of the text) are even considerably simpler.
There are two known linear time serial algorithms for this extensively studied problem, due to [em  77] and [kmp Recall that every parallel linear algorithms is, in particular, a linear time serial algorithm. The present result is stronger than theirs in the sense that it gives a parallel linear algorithm while theirs serial algorithms do not seem to imply satisfactory parallel linear algorithms. Moreover, our algorithm is not more complicated than theirs. Some parts of it (particularly, the analysis of the text) are even considerably simpler.
57 pages, Paperback
Published January 1, 2024
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
No one has reviewed this book yet.