[C/C++] BOJ 5525 :: IOIOI

BOJ 5525 :: IOIOI

문제 링크 : https://www.acmicpc.net/problem/5525

나의 풀이

KMP 방식으로 일치하는 단어가 있는지 탐색한 후, 있으면 값을 증가시킨다.

KMP에 대한 설명 : https://j2wooooo.tistory.com/119?category=1038656

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_5525/BOJ_5525.cpp

// 백준알고리즘 5525번 :: IOIOI
#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int N, ssize;
string sentence;
string pattern;
 
vector<int> makeTable()
{
    int psize = (int)pattern.size();
    vector<int> Table(psize, 0);
    int j = 0;
 
    for (int i = 1; i < psize; i++)
    {
        while (j != 0 && pattern[i] != pattern[j])
            j = Table[j - 1];
        if (pattern[i] == pattern[j])
            Table[i] = ++j;
    }
    return Table;
}
int KMP()
{
    int ans = 0;
    vector<int> Table = makeTable();
    int psize = (int)pattern.size();
    int j = 0;
    for (int i = 0; i < ssize; i++)
    {
        while (j != 0 && sentence[i] != pattern[j])
            j = Table[j - 1];
        if (sentence[i] == pattern[j])
        {
            if (j == psize - 1)
            {
                ans++;
                j = Table[j];
            }
            else j++;
        }
    }
    return ans;
}
 
int main()
{
    cin >> N >> ssize >> sentence;
 
    for (int i = 0; i < (2 * N + 1); i++)
    {
        if ((i % 2) == 0) pattern.push_back('I');
        else pattern.push_back('O');
    }
 
    int ans = KMP();
    cout << ans;
    return 0;
}