AOJ 0571 JJOOII

文字列を圧縮(文字の種類+その文字が何個あるかの情報に)する
圧縮した文字列にJOIがあったら、JOI列の条件を満たしているか確認してレベル計算
O(N)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char s[1000010];
char t[1000010];
int tn[1000010];
int tl;
int l;
int main(){
	scanf("%s", s);
	l = strlen(s);
	char p;
	int a;
	a = 1;
	p = s[0];
	tl = 0;
	s[l] = 'A';
	for(int i = 1;i < l + 1; i++){
		if(s[i] == p){
			a++;
		}else{
			t[tl] = p;
			tn[tl] = a;
			a = 1;
			p = s[i];
			tl++;
		}
	}
	int ans =0;
	for(int i = 0; i <= tl-2; i++){
		if(t[i] == 'J' && t[i+1] == 'O' && t[i+2] == 'I'){
			if(tn[i] < tn[i+1] || tn[i+2] < tn[i+1])
				continue;
			ans = max(ans, min(tn[i], min(tn[i+1], tn[i+2])));
		}
	}
	printf("%d\n", ans);
	return 0;
}