Optimal parallel algorithms for string matching

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 ⩽ n/log n (i.e., t ⩾ log n).† (2) for PRAM: pt = O(n) for p ⩽ n/log2 n (i.e., t ⩾ log2 n). (3) For WRAM: t = constant for p = n1 + ε and any ε > 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.†All logarithms are to the base 2