[C++] 찾기(KMP) - 1786

KMP 알고리즘

---

해당 문제는 KMP 알고리즘만 알고 있으면 아주 간단하게 해결할 수 있는 문제입니다.

 

vector<int> makeTable(string pattern)
{
	vector<int> table(pattern.size(), 0);

	int head = 0;
	for (int tail = 1; tail < pattern.size(); tail++)
	{
		while (head > 0 && pattern[head] != pattern[tail])
			head = table[head - 1];

		if (pattern[head] == pattern[tail])
		{
			table[tail] = ++head;
		}
	}

	return table;
}

table  생성 함수

 

 

void KMP(string str, string pattern)
{
	vector<int> table = makeTable(pattern);
	vector<int> N;

	int P = 0;
	for (int S = 0; S < str.size(); S++)
	{
		while (P > 0 && pattern[P] != str[S])
			P = table[P - 1];

		if (pattern[P] == str[S])
		{
			if (P == pattern.size() - 1)
			{	// pattern의 시작 위치를 vector에 넣어줌
				N.push_back(S - pattern.size() + 2);
				P = table[P];
			}
			else
				++P;
		}
	}

	cout << N.size() << '\n';
	for (int i = 0; i < N.size(); i++)
		cout << N[i] << '\n';
}

KMP 함수

 

int main()
{
	string str;
	string pattern;

	getline(cin, str);
	getline(cin, pattern);

	KMP(str, pattern);

	return 0;
}