[5525번] IOIOI

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. KMP 알고리즘 :: http://www.crocus.co.kr/559

이문제는 전형적인 KMP 알고리즘으로 해결이 가능한 문제이다.

kmp에 대한 내용은 위 링크를 참조하면 된다.

Pn을 구하는 방법에 대해서는 다음과 같다.

우선, string에 I를 추가해두고  n의 크기에 따라 OI를 추가해주면 된다.

이때 결과적으로 만들어진 Pn 이라는 string은 KMP 알고리즘에서 찾기위해 쓰이는 문자열로 이용될 것이다.

아래 주석을 달아두었는데, 저 주석은 문자열의 몇번째 위치에서 Pn이 나타나는지 모아둔 벡터이다. 

소스 코드 : 

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
 
using namespace std;
 
vector<int> getPi(string p)
{
    int m = (int)p.size();
    int j = 0;
 
    vector<int> pi(m, 0);
 
    for (int i = 1; i< m; i++) {
        while (j > 0 && p[i] != p[j])
            j = pi[j - 1];
        if (p[i] == p[j])
            pi[i] = ++j;
    }
    return pi;
}
 
vector<int> kmp(string s, string p)
{
    vector<int> ans;
    auto pi = getPi(p);
    int n = (int)s.size(), m = (int)p.size(), j = 0;
    for (int i = 0; i < n; i++) {
        while (j>0 && s[i] != p[j])
            j = pi[j - 1];
        if (s[i] == p[j]) {
            if (j == m - 1) {
                ans.push_back(i - m + 1);
                j = pi[j];
            }
            else {
                j++;
            }
        }
    }
    return ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    
    string Pn = "I";
 
    for (int i = 0; i < n; i++)
        Pn += "OI";
 
    scanf("%d", &n);
    
    string str;
    cin >> str;
 
    vector<int> matched = kmp(str, Pn);
 
    printf("%d\n", (int)matched.size());
 
    /*
    for (auto i : matched)
        printf("%d ", i + 1);
    */
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>