O(k) Parallel Algorithms for Approximate String Matching

Neural, Parallel, and Scientific Computations, 1 (1993) 443-452.

Alden H. Wright & Yi Jiang
Department of Computer Science
University of Montana
Missoula, MT 59812
May 25, 1993


Given a text string $T$ of length $n$, a shorter pattern string $A$ of length $m$, and an integer $k$, an simple straightforward $O(k)$ parallel algorithm for finding all occurrences of the pattern string in the text string with at most $k$ differences (as defined by edit distance) is presented. The algorithm uses the priority CRCW-PRAM model of computation and $(n-m+k+2) \times m = O(n \times m)$ processors. Over recent decades, {\it the k-differences string matching problem} received much attention in the research literature, due to its importance in molecular biology, text retrieval, and other types of applications. Based on a variation of Ukkonen's algorithm, this paper presents several different ways of achieving a time complexity of $O(k)$ for solving this problem with different CRCW-PRAM assumptions.
Key words approximate string matching
edit distance