09/06/15 16:04:24
A～Zまでの文字を並べて得られる列を文字列と呼ぶ。
文字列x,yに対し、関数d(x,y)を次のように定義する。
【定義】
文字列xに対して、挿入・削除・置換（詳細後述）を繰り返して、文字列yに変換する場合の、挿入・削除・置換の最小実行回数をd(x,y)とする。
[挿入]
文字列xに場所を指定しつつ、一文字だけ文字を挿入する。たとえば、文字列abdの2文字目より後ろにcを挿入するとabcdとなる。
[削除]
文字列xの場所を指定し、一文字だけ文字を削除する。たとえば文字列abecの3文字目を削除すると、abcとなる。
[置換]
文字列xの場所と、置換後の文字を指定し、一文字だけ置換する。たとえば文字列abedの3文字目をcに置換すると、abcdとなる。
（関数値の例）
d("abdef", "abcdef") = 1
このとき任意の文字列x,y,zに対し、d(x,y) + d(y,z) ≧ d(x,z)を示せ。