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)で求めることが出来る。