5525 IOIOI 백준

#include <string>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    //입력값 모두 받기
    int n, s;
    string str;
    scanf("%d %d", &n, &s);
    getchar();
    getline(cin, str);
 
    // 비교할 패턴 만들기
    vector<char> pattern;
    int patternLen = n * 2 + 1;
    for (int i = 1; i <= n; i++) {
        pattern.push_back('I');
        pattern.push_back('O');
    }
    pattern.push_back('I');
 
    //패턴의 pi 배열 만들기
    int cmp = 0;
    vector<int> pi(patternLen + 1, 0);
    for(int i = 1; i < patternLen; i++) {
        while (cmp > 0 && pattern[cmp] != pattern[i])
            cmp = pi[cmp - 1];
        if (pattern[cmp] == pattern[i])
            pi[i] = ++cmp;
    }
    // KMP 방식 진행
    int pidx = 0, strL = str.size(), tmp = 0;
    for (int i = 0; i < strL; i++) {
        while (pidx > 0 && str[i] != pattern[pidx])
            pidx = pi[pidx - 1];
        if (str[i] == pattern[pidx]) {
            if (pidx == patternLen - 1) {
                tmp++;
                pidx = pi[pidx];
            }
            else
                pidx++;
        }
    }
    //결과 출력
    printf("%d", tmp);
}