1983 Reports

# Optimal Parallel Algorithms for String Matching

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.

## Subjects

## Files

- cucs-074-83.pdf application/pdf 508 KB Download File

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-074-83
- Published Here
- October 26, 2011