Combinatorial - Edit Distance (Levenshtein Distance)

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

編集距離

2つの文字列 s1s2 の編集距離(レーベンシュタイン距離)を求めて下さい。

編集距離とは、以下3種類の操作によって、1つの文字列を別の文字列に変形するのに必要な手順の最小回数です:

  • 挿入: 文字列に1つの文字を挿入する。
  • 削除: 文字列から1つの文字を削除する。
  • 置換: 文字列の中の1文字を別な文字に置き換える。

入力

s1
s2

2つの文字列 s1, s2 がそれぞれ1行目と2行目に与えられる。文字列はアルファベットの小文字で構成されている。

出力

編集距離を1行に出力する。

制約

  • 1 ≤ s1 の長さ ≤ 1000
  • 1 ≤ s2 の長さ ≤ 1000

入力例 1

acac
acm

出力例 1

2

入力例 2

icpc
icpc

出力例 2

0