Optimal parallel algorithms for string matching. (English) Zbl 0588.68022

Galil, Zvi

Inf. Control 67, 144-157 (1985).

Let WRAM [PRAM] be a parallel computer with p processors (RAMs) which share a common memory and are allowed simultaneous reads and writes [only simultaneous reads]. The only type of simultaneous writes allowed is a simultaneous AND: a subset of the processors may write 0 simultaneously into the same memory cell. Let t be the time bound of the computer. We design below families of parallel algorithms that solve the string matching problem with inputs of size n (n is the sum of lengths of the pattern and the text) and have the following performance in terms of p, t and n: (1) For WRAM: pt-O(n) for \(p\leq n/\log n\) (i.e., \(t\geq \log n)\). (2) For PRAM: \(pt=O(n)\) for \(p\leq n/\log^ 2n\) (i.e., \(t\geq \log^ 2n)\). (3) For WRAM: \(t=cons\tan t\) for \(p=n^{1+\epsilon}\) and any \(\epsilon >0\). (4) For WRAM: \(t=O(\log n/\log \log n)\) for \(p=n\). Similar families are also obtained for the problem of finding all initial palindromes of a given string.

MSC:

68Q25

Analysis of algorithms and problem complexity

Keywords:

parallel computation; WRAM; PRAM