ダメラウ・レーベンシュタイン距離
次は、真のダメラウ・レーベンシュタイン距離を求めるアルゴリズムである。このアルゴリズムでは、アルファベットに含まれる全文字 Σ の個数 | Σ | {\displaystyle |\Sigma |} が必要になる。成分が [0, |Σ|) に含まれる配列を使うからである。擬似コードは:
非制限ダメラウ・レーベンシュタイン距離を求める正しいアルゴリズムを作るには次のことに注意する:1度交換された文字がそのあと2度と編集されないような編集操作の最適配列が存在する(交換のコスト W T {\displaystyle W_{T}} が挿入のコスト W I {\displaystyle W_{I}} と削除のコスト W D {\displaystyle W_{D}} の平均以上つまり 2 W T ≥ W I + W D {\displaystyle 2W_{T}\geq W_{I}+W_{D}} の場合に成立する)。