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## ABSTRACT:

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 PRAM CRCW-PRAM |