[백준/BOJ] 백준 1786번 : 찾기

www.acmicpc.net/problem/1786

1786번: 찾기

KMP알고리즘을 이용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

string t, p;
vector<int> pi(1000000, 0);
vector<int> ret;

//KMP알고리즘을 이용한다
//알고리즘 문제해결 전략2 책 KMP알고리즘 공부 실습
void Make_pi()
{
	int start = 1;
	int matched = 0;
	int p_size = p.size();

	while (start + matched < p_size)
	{
		if (p[start + matched] == p[matched])
		{
			matched++;
			pi[start + matched - 1] = matched;
		}

		else
		{
			if (matched == 0)
			{
				start++;
				matched = 0;
			}

			else
			{
				start += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
}

void Kmp()
{
	int start = 0;
	int matched = 0;
	int t_size = t.size();
	int p_size = p.size();

	while (start <= t_size - p_size)
	{
		if (matched < p.size() && t[start + matched] == p[matched])
		{
			matched++;

			if (matched == p.size())
				ret.push_back(start);
		}

		else
		{
			if (matched == 0)
			{
				start++;
				matched = 0;
			}

			else
			{
				start += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	getline(cin, t);
	getline(cin, p);

	Make_pi();
	Kmp();

	cout << ret.size() << "\n";
	for (int i = 0; i < ret.size(); i++)
		cout << ret[i] + 1 << " ";

	return 0;
}