2015年2月14日土曜日

yukicoder 150 "良問"(良問とは言っていない

問題

http://yukicoder.me/problems/344
要するに入力された文字列sを、
先頭から見たときに"good","problem"がこの順に見つかるようにするためには何文字変更するべきかを求める問題。
100個の100字以内の文字列に対して探さなければならない。

解法

tbl1[i] = str[0~i]の中で"good"とのハミング最小距離
tbl2[i] = str[i~n-1]の中で"problem"とのハミング最小距離
とすると,tbl1[i]+tbl2[i+1]で求めることが出来る。

tbl1[i] = min(tbl[i-1], haming("good", str[i-3~i])
で求められるのでO(4・n) = O(n)
tbl2も同様にして求めることが出来る。
なので全体としてO(n)で求めることが出来る。


0 件のコメント:

コメントを投稿