問題
サイズNの文字列AとBが与えられる。A内のある文字を選び、それを先頭に持ってくるという操作だけができる。AからBにするのに必要な操作数の最小値を求めよ。AからBにできない場合は-1を返す。
解法
AとBの後ろの要素を比較する。同じだった場合は、次の要素を比較し、違った場合は一致するまでAの要素を後ろ側から探索する。(文字数)-(一致した回数)が答えとなる。
計算量
サイズNの文字列AとBが与えられる。A内のある文字を選び、それを先頭に持ってくるという操作だけができる。AからBにするのに必要な操作数の最小値を求めよ。AからBにできない場合は-1を返す。
AとBの後ろの要素を比較する。同じだった場合は、次の要素を比較し、違った場合は一致するまでAの要素を後ろ側から探索する。(文字数)-(一致した回数)が答えとなる。