Efficient Parallel Output-Sensitive Edit Distance

Xiangyun Ding, Xiaojun Dong, Yan Gu +2

Given two strings $A[\mathrm{1..}n]$ and $B[\mathrm{1..}m]$, and a set of operations allowed to edit the strings, the edit distance between $A$ and $B$ is the minimum number of operations required t…