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; }