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.