ダメラウ・レーベンシュタイン距離
d a , b  ( i , j − 1 ) + 1 {\displaystyle \operatorname {d} _{a,b}(i,j-1)+1} : b [ 1 , j ] {\textstyle b[1,j]} が、 b [ 1 , j − 1 ] {\textstyle b[1,j-1]} に1回の挿入をすることで得られたと見なして編集回数を 1 {\textstyle 1} だけ増やす
d a , b  ( i − 1 , j − 1 ) + 1 ( a [ i ] ≠ b [ j ] ) {\textstyle \operatorname {d} _{a,b}(i-1,j-1)+1_{(a[i]\neq b[j])}} : a [ i ] {\textstyle a[i]} と b [ j ] {\textstyle b[j]} が一致する場合には、 a [ 1 , i ] {\textstyle a[1,i]} と b [ 1 , j ] {\textstyle b[1,j]} の間の距離は a [ 1 , i − 1 ] {\textstyle a[1,i-1]} と b [ 1 , j − 1 ] {\textstyle b[1,j-1]} の間の距離に等しいので編集回数を変更しない。 a [ i ] {\textstyle a[i]} と b [ j ] {\textstyle b[j]} が一致しない場合には、 a [ i ] {\textstyle a[i]} を b [ j ] {\textstyle b[j]} に、あるいは b [ j ] {\textstyle b[j]} を a [ i ] {\textstyle a[i]} に置換したと見なして編集回数を 1 {\textstyle 1} だけ増やす
したがって、1つの部分文字列を2回以上編集する2つの対称な方法:
隣接文字を交換して任意の個数の文字をその間に挿入する
文字列を削除し、その削除によって新たに隣り合うことになった隣接文字を交換する
のいずれかだけを考えればよい。このアイディアを素直に実行するアルゴリズムは、文字列の長さ M {\displaystyle M} および N {\displaystyle N} に対して O ( M N ⋅ max ( M , N ) ) {\displaystyle O(MN\cdot \max(M,N))} の計算複雑性を持つ。ローランスとワグナーのアイディアを使ったアルゴリズムでは、最悪の場合でも O ( M N ) {\displaystyle O(MN)} に改善される。
Bitapアルゴリズムを、隣接交換を処理するように変更できる。この例については参考文献の情報収集の節を見よ。