第８回日本情報オリンピック 本選 「IOIOI」

m<=1000000から察するに、オーダーはO(M).

解法の詳細は、連続する"IOI"の数を計算する。（たとえば、IOIOIのとき2）
その値をtとすると、ans += max(0,t-n+1)で答えが求まる。
少し考えればできる問題。

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

int main(){

	while(1){
	int n,m;
	char s[1000005];
	scanf("%d",&n);
	if(n == 0)break;
	scanf("%d",&m);
	scanf("%s",&s);

	int ren = 0;
	int ans = 0;

	for(int i = 0;i < m - 2;i++){
		if(s[i] == 'I' && s[i+1] == 'O' && s[i+2] == 'I'){
			ren++;
			i++;
		}else{
			if(ren != 0)ans += max(0,ren - n + 1);
			ren = 0;
		}
	}
		if(ren != 0)ans += max(0,ren - n + 1);
	printf("%d\n",ans);
	}
	return 0;

}