5525 IOIOI

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

KMP 알고리즘을 이용하여 패턴이 몇번 나타나는지 찾아준다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main()
{
    int n,m;
    string s,p="I";
    cin>>n>>m>>s;
    for(int i=0;i<n;i++) p+="OI";
    n=2*n+1;
 
    vector<int> pi(n);
    pi[0]=0;
    for(int i=1,j=0;i<n;i++)
    {
        while(j>0 && p[i]!=p[j]) j=pi[j-1];
        if(p[i]==p[j]) pi[i]=++j;
        else pi[i]=0;
    }
 
    int ans=0;
    for(int i=0,j=0;i<m;i++)
    {
        while(j>0 && s[i]!=p[j]) j=pi[j-1];
        if(s[i]==p[j])
        {
            if(j==n-1) ans++,j=pi[j];
            else j++;
        }
    }
 
    cout<<ans;
    return 0;
}