[BOJ]16916번: 부분 문자열 (c++)

www.acmicpc.net/problem/16916

16916번: 부분 문자열

 

KMP 문자열 알고리즘

#include <iostream>
#include <vector>

using namespace std;

// Prefix Index 배열 만들기
vector<int> make_pi(string &pattern)
{
	int len = pattern.size();
	vector<int> pi(len);

	for (int i = 1, j = 0; i < len; ++i)
	{
		while (j > 0 && pattern[i] != pattern[j])
		{
			j = pi[j - 1];
		}

		if (pattern[i] == pattern[j])
		{
			pi[i] = ++j;
		}
	}
	return pi;
}

// kmp 알고리즘으로 pattern이 parent에 포함하는지 여부 판별
bool kmp(string &parent, string &pattern)
{
	vector<int> pi = make_pi(pattern);
	int parent_size = parent.size();
	int pattern_size = pattern.size();

	for (int i = 0, j = 0; i < parent_size; ++i)
	{
		while (j > 0 && parent[i] != pattern[j])
		{
			j = pi[j - 1];
		}

		if (parent[i] == pattern[j])
		{
			if (j == pattern_size - 1)
			{
				return true;
			}
			else
			{
				++j;
			}
		}
	}
	return false;
}

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	string parent, pattern;
	cin >> parent >> pattern;

	// 포함여부 출력 - kmp 알고리즘
	cout << kmp(parent, pattern);

	return 0;
}

 

 

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.
두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다.

 

두 문자열의 크기는 100만 이하이다. 

만약 이것을 단순비교하면 O(N*M) = O(1억)이 될것이다. 

 

따라서 KMP, 라빈-카프, 보이어-무어 등 문자열 알고리즘을 이용하여 

더 효율적인 시간복잡도로 풀어야한다. 

나는 KMP알고리즘으로 풀었고, 이때 시간복잡도는 O(N + M) 이다.

 

이 문제에 대한 자세한 설명은 내가 참고한 다른 두 블로그를 링크하는 것으로 갈음하겠다

알고리즘을 순수히 그대로 이용한 것이므로...

 

 

30. KMP(Knuth-Morris-Pratt) 알고리즘

 

KMP : 문자열 검색 알고리즘