Optimal parallel pattern matching in strings. (English) Zbl 0588.68023

Vishkin, Uzi

Inf. Control 67, 91-113 (1985).

Given a text of length n and a pattern of length m, we present a parallel linear algorithm for finding all occurrences of the pattern in the text. The algorithm runs in O(n/p) time using any number of \(p\leq n/\log m\) processors on a concurrent-read concurrent-write parallel random-access machine.

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q05	Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

parallel computation; parallel linear algorithm; concurrent-read concurrent-write parallel random-access machine