yukicoder : No.252 "良問"(良問とは言っていない (2)

問題文をよく読まずにWAしたが、最終的にはなんとかFA。
http://yukicoder.me/problems/387

問題

文字列が良問であるとは、以下の条件を満たすものをいう。

• 部分文字列として"good"及び"problem"両方を含む。
• 先頭から見て最初に見つかる"good"が"problem"より先に見つかる。

文字列Sを良問にするのに書き換えなければならない最小文字数を求めよ。

解法

まず各位置が"problem"の先頭であると仮定した場合、それぞれそこから7文字を見て何文字置き換えれば"problem"になるかを求める。
さらに、続けて各位置以降における上記値の最小値、すなわち以後登場する文字列のうちどこかに"problem"を生成する最小文字列置換数を求める。

同様に、各位置が"good"の先頭であると仮定した場合、それぞれそこから4文字を見て何文字置き換えれば"good"になるかを求める。
この時、以下の和が解の候補となるのでその最小値を求めよう。
"good"の先頭がSのx文字目とすると：

• S[x..(x+3)]を置き換えてgoodにするのに必要な最小文字列置換数
• S[(x+4)..|S|]内に"problem"を生成するのに必要な最小文字列置換数（最初の前処理で計算済み)
• "good"の前に"problem"があると条件を満たせないので、それらを見つけたら1個当たり1文字文字を置き換えて"problem"を壊さないといけない。よってS[1..(x-1)]中の"problem"の数。

int T;
string S;
int G[1010101];
int P[1010101];
int M[1010101];

int NG[1010101],NP[1010101];
int L;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	int mp=10000000;
	while(T--) {
		cin>>S;
		L=S.size();
		FOR(i,L+10) {
			NP[i]=(i)?NP[i-1]:0;
			M[i]=1010100;
			if(i+6>=L) P[i]=1010100;
			else {
				P[i]=0;
				FOR(x,7) if(S[i+x]!="problem"[x]) P[i]++;
				if(P[i]==0) NP[i]++;
			}
		}
		int mi=1010;
		for(i=L;i>=0;i--) M[i]=min(P[i],M[i+1]);
		FOR(i,L-4) {
			NG[i]=(i)?NG[i-1]:0;
			int cnt=0;
			FOR(x,4) if(S[i+x]!="good"[x]) cnt++;
			mi=min(mi,cnt+M[i+4]+((i>=7)?NP[i-7]:0));
		}
		cout<<mi<<endl;
	}
}

まとめ

先頭という条件がややこしい。
しかしこのタグは何なんだろう。