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
",ans);
	}
	return 0;

}