백준 5525번 IOIOI

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

 

KMP로 풀었는데 포함되었는지 아닌지를 묻는 것이 아니고 몇번 포함되었는지를 묻는 상황.

한번 일치한 이후에는 그 앞으로 부터 접두사와 일치하는 개수 바로 다음 인덱스로 다시 조사해야하므로 (i가 끝날떄까지)

j = table[j] 에서 다시 시작해야하고, 일치할 때마다 count 증가시켜서 세면 끝.

(table[j-1]이 아닌것은 자신도 일치하였기 떄문에 포함됨)

#include<iostream>
#include<vector>


using namespace std;

int N, M;

vector<int> makeTable(string str)
{
	int size = str.size();
	int j = 0;
	vector<int> table(size, 0);
	
	for (int i = 1; i < size; i++)
	{
		while (j > 0 && str[j] != str[i])
		{
			j = table[j - 1];
		}

		if (str[j] == str[i])
		{
			table[i] = ++j;
		}
	}
	return table;

}

int  KMP(string str1, string str2)
{
	int size1 = str1.size();
	int size2 = str2.size();
	int count = 0;

	vector<int> table = makeTable(str2);
	int j = 0;
	for (int i = 0; i < size1; i++)
	{
		while (j > 0 && str1[i] != str2[j])
		{
			j = table[j - 1];
		}
		if (str1[i] == str2[j])
		{
			if (j == size2 - 1)
			{
				j = table[j];
				count++;
			}
			else
			{
				j++;
			}
		}
	}
	return count;
}

int main(void)
{

	cin >> N >> M;
	string str;
	cin >> str;

	string str2;
	for (int i = 0; i < 2 * N + 1; i++)
	{
		if (i % 2 == 0)
		{
			str2 += 'I';
		}
		else
		{
			str2 += 'O';
		}

	}
	
	cout << KMP(str, str2) << endl;


}