Edit Distance

問題文

文字列 $S$ と文字列 $T$ が与えられます。

$S$ と $T$ のレーベンシュタイン距離を求めてください。

制約

• $1 \leq |S| , |T| \leq$ $\textcolor{red}{2 \times 10^5}$
• $S$ および $T$ は英小文字からなる文字列

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを一行に出力せよ。

入力例1

出力例1

3

次の3回の操作で、$S$ を $T$ に一致させることができます。

• 先頭の k を s に置き換えます。
• $5$ 文字目の e を i に置き換えます。
• 末尾に g を挿入します。

$2$ 回以下の操作で一致させることはできないため、答えは $3$ です。

入力例2

出力例2

1

$2$ 文字目の b を削除すると、$S$ と $T$ が一致します。

入力例3

出力例3

0

$S$ と $T$ は最初から一致しているため、操作は必要ありません。