[5525] IOIOI

https://www.acmicpc.net/problem/5525

5525번: IOIOI

선형에 풀기 위해서는 단순히 substr을 비교하는것이 아니라, 현재까지 확인한 IOIOI...문자열의 길이를 저장해야한다.

올바른 괄호를 판별하는 스택문제와 유사하다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, S, ans, cur;

string s;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> S >> s;

    int i;

    for (i = 0; i < S; i++) {

        if ((cur & 1) && s[i] == 'O')

            cur++;

        else if ((~cur & 1) && s[i] == 'I')

            cur++;

        else

            cur = (s[i] == 'I');

        if (s[i] == 'I' && cur >= 2 * n + 1) ans++;

    }

    cout << ans;

    return 0;

}

---