[ 백준 / C++ ] 5525 : IOIOI

[ 문제 ]

 

5525번: IOIOI (acmicpc.net)

 

[ 접근방법 ]

 

KMP 알고리즘을 활용한다.

 

이를 통해 O(N + M)에 해결 가능하다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, ans = 0;
    string a, b;

    cin >> n >> m >> a;

    b = "I";
    for(int i = 0; i < n; i++)b += "OI";

    n = 2 * n + 1;
    vector<int> kmp(n);

    for(int i = 1, j = 0; i < n; i++){
        while(j && b[i] != b[j])j = kmp[j - 1];
        if(b[i] == b[j])kmp[i] = ++j;
    }

    for(int i = 0, j = 0; i < m; i++){
        while(j && a[i] != b[j])j = kmp[j - 1];
        if(a[i] == b[j])j++;
        if(j == n){
            ans++;
            j = kmp[j - 1];
        }
    }

    cout << ans;

    return 0;
}