Problem
テキスト文字列を指定します。これを使用して次の操作を実行できます。
1.文字列の 1 つの文字を別の文字に置き換えます。
2.任意の1文字を削除します。
3.文字列内の任意の位置に任意の文字を挿入します。
たとえば、文字列「JUICE」の最初の操作を使用すると、 2 番目の操作 - 文字列「OK」を使用すると文字列「SUK」を取得でき、3 番目の操作 - 文字列「STOCK」を使用すると文字列「SUK」を取得できます。
ある文字列から別の文字列を取得するために使用できるこのような操作の最小数は、編集コストまたはレーベンシュタイン距離と呼ばれます。
指定された 2 つの文字列のレーベンシュタイン距離を求めます。
入力
プログラムは 2 つの文字列を入力として受け取ります。各文字列の長さは 1000 文字を超えず、文字列は大文字のラテン文字のみで構成されます。
出力
単一の数値を出力するために必要 –指定された文字列のレーベンシュタイン距離。
<本体>
| 入力 |
出力 |
|
ABCDEFGH
ACDEXGIH
|
3 |