Efficient Parallel Algorithms for String Editing and Related Problems
Alberto Apostolico, Mikhail J. Atallah, Lawrence L. Larmore, Scott McFaddin · SIAM Journal on Computing · 1990
The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a symbol from x, the insertion of a symbol in x or the substitution of a symbol of x with another symbol. This problem has a well-known $O(|x||y|)$ time-sequential solution. Efficient PRAM parallel algorithms for the string editing problem are given. If $m = \min (|x|,|y|)$ and $n = \max (|x|,|y|)$, then the CREW bound is $O(\log m \log n)$ time with $O({{mn} / {\log m}})$ processors. The CROW bound is $O(\log n(\log \log m)^{2})$ time with $O(mn/ \log \log m)$ processors. In all algorithms, space is $O(mn)$.