No.225 文字列変更(medium)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 145
作問者 : drken1215drken1215
9 ProblemId : 610 / 出題時の順位表

問題文

長さ\(n\)の文字列\(S\)と長さ\(m\)の文字列\(T\)が与えられます。文字列を構成する各文字は、'a'~'z'です。
今、\(S\)に以下の3種類の操作のいずれかを順次実施して\(T\)に変換したいです。
そのような一連の操作のうち、操作回数の最小となるものについて、その最小値を出力するプログラムを書いて下さい。

(操作)
【変更】 \(S\)の中から文字\(S\)[ i ]を1個選んで、その文字を'a'~'z'のいずれかの好きな文字に変更します。
【削除】 \(S\)の中から文字\(S\)[ i ]を1個選んで、その文字を削除します。削除によって空文字列になることも許容します。
【挿入】 \(S\)の好きな箇所に、'a'~'z'のいずれかの文字を挿入します。特に、Sの先頭や最後尾に文字を追加することもできます。

入力

\(n\) \(m\)
\(S\)
\(T\)

一行目に文字列\(S\), \(T\)の長さを表す整数\(n\), \(m\)で空白区切りで与えられます。
続く二行目、三行目には、文字列\(S\), \(T\)がそれぞれ与えられます。

\(1 \leq n, m \leq 1000\)
\(S\), \(T\)は、'a'~'z'から構成される文字列です

出力

答えを1行に出力してください。

サンプル

サンプル1
入力
9 9
abcdefghi
acdefxhij
出力
3

2文字目のbを削除
abcedfghi -> acdefghi
最後尾にjを追加
acdefghi -> acdefghij
6文字目のgをxに変更
acdefghij -> acdefxhij

サンプル2
入力
3 4
abc
addc
出力
2

サンプル3
入力
14 16
pirikapirirara
poporinapeperuto
出力
10

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。