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

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