Problem

3 /5


ダメラウ・レーベンシュタイン距離

Problem

最も一般的な入力ミスの 1 つは、たとえば「program」という単語の代わりに、隣接する 2 つの文字が入れ替わることです。 「プログラム」という単語が入力されます。レーベンシュタイン距離では、そのようなタイプミスは考慮されません。レーベンシュタイン距離を計算するとき、1 つの順列は 2 つの編集 (文字の削除と挿入など) としてカウントされます。
 
ダメラウ・レーベンシュタイン距離を計算する場合、文字の置換、挿入、削除の操作に加えて、隣接する 2 つの文字を並べ替える操作も許可されます。同時に、再配置された文字の間に他の文字を挿入することはできません。
 
指定された 2 つの文字列のダメラウ-レーベンシュタイン距離を決定します。
  <本体>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

入力 出力
XABCDE
ACBYDF
 4