백준 1786번: 찾기

[문제 링크]

1786번: 찾기

---

입력받는 문자열 T, P의 최대 길이가 100만으로 굉장히 길기 때문에 O(NM) 알고리즘으로 풀 수 없다.

따라서 시간복잡도가 O(N+M)인 KMP-algorithm을 구현하여 풀었다.

 

추가로 공백을 포함하는 문자열을 입력받기 위해 cin 함수가 아닌 getline(cin, str) 함수를 사용하였다.

---

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

vector<int> getPartialMatch(const string& P)
{
	int Plen = P.length();
	vector<int> pi(Plen, 0);

	int begin = 1, matched = 0;
	while (begin + matched < Plen)
	{
		if (P[begin + matched] == P[matched])
		{
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}

vector<int> KMPsearch(const string& T, const string& P)
{
	int Tlen = T.length(), Plen = P.length();

	vector<int> pos;
	vector<int> pi = getPartialMatch(P);

	int begin = 0, matched = 0;
	while (begin <= Tlen - Plen)
	{
		if (T[begin + matched] == P[matched])
		{
			matched++;
			
			if (matched == Plen)
				pos.push_back(begin + 1);
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pos;
}

int main(void)
{
	string T, P;

	getline(cin, T);
	getline(cin, P);

	vector<int> result = KMPsearch(T, P);

	cout << result.size() << endl;
	
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << ' ';

	return 0;
}

알고리즘 200일 프로젝트 - 137 day