Academic Commons


Optimal Parallel Algorithms for String Matching

Galil, Zvi

Let WRAM [PRAM] be a parallel computer with p processors (RAM's) 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: several processors may write O 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 for p ≤ n/log n. 2. For PRAM: pt = O(n) for P ≤ n/log2n. 3. For WRAM: t = constant for p = nl+ ε and any ε > O. 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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-074-83
Published Here
October 26, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.