編集距離 (Edit Distance)
2つの文字列の編集距離（edit distance）は、一方の文字列をもう一方に変換するために必要な操作の最小回数を指します。許可される操作は次の3つです:
- 文字を1つ追加する
- 文字を1つ削除する
- 文字を1つ置き換える
たとえば、 と の編集距離は2です。これはまず を に置き換え、その後 を追加すれば変換できるためです。
与えられた2つの文字列に対して、その編集距離を求めるのが課題です。
Input
最初の行に最初の文字列、次の行に2つ目の文字列が与えられます。各文字列の長さは1000文字を超えないことが保証されています。
Output
2つの文字列の編集距離を示す整数を1つ出力します。
Examples
入力 | 出力 |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB