0538-IOIOI

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0538
Boyer-Mooreのアルゴリズムを用いて数え上げ。
規則性を使えばもっと早くなりそうだけど…。

#include <cstring>
#include<cstdio>
using namespace std;
char strs[1000002];
char mkh[1000002];
int n,m,r,c,t;
int main() {
	for(;~scanf("%d%d",&n,&m);){
		if(n==0) break;
		scanf("%s",strs);
		mkh[0]='I';
		c=0;r=2*n+1;
		for(int i=0;i<n;i++){
			mkh[i*2+1]='O';
			mkh[i*2+2]='I';
		}
		for(int i=r-1;i<m;){
			if(strs[i]=='I'){
				t=0;
				int j;
				for(j=0;j<r;j++){
					if(strs[i-r+j+1]!=mkh[j]){
						if(strs[i-r+j+1]!='I'&&strs[i-r+j+1]!='O'){i+=j-2;}
						t=1;break;
					}
				}
				if(t==0) {c++;i+=2;}
				if(t!=0) {i+=2;}
			}else if(strs[i]=='O'){
				i++;
			} else{
				i+=r;
			}
		}
		printf("%d\n",c);
	}
	return 0;
}