[백준 1786][💛1] 찾기 (KMP)

🚀 난이도

💛 골드 1

🚀 문제

https://www.acmicpc.net/problem/1786

이 문제에서 설명하는 것 자체가 KMP 알고리즘이다.

🚀 내 풀이

📌 KMP 알고리즘 에 대한 자세한 설명은 링크로 https://ansohxxn.github.io/algorithm/kmp/

KMP 알고리즘의 대표적인 두 코드로 제출을 했다. 자세한 설명은 위 링크에 다 기재해두었기 때문에 이 포스트에선 설명을 생략하겠다.

🔥 첫 번째 풀이 ⭕

#include <bits/stdc++.h>

using namespace std;

vector<int> Fail(string pattern) {
	int m = pattern.length();
	vector<int> pi(m); // partial match table

	int begin = 1;
	int matched = 0;
	pi[0] = 0;
	while (begin + matched < m) {
		if (pattern[begin + matched] == pattern[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> KMP(string pattern, string text) {
	int m = pattern.length();
	int n = text.length();
	vector<int> pos;
	vector<int> pi = Fail(pattern);

	int begin = 0;
	int matched = 0;
	while (begin + m <= n) {
		if (matched < m && text[begin + matched] == pattern[matched]) {
			matched++;

			if (matched == m)
				pos.push_back(begin + 1); // 위치를 1 부터 치기 때문에 +1 해줌
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pos;
}

int main() {
	//freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	// 공백을 포함하는 문자열 입력
	string text;
	getline(cin, text);
	string pattern;
	getline(cin, pattern);

	vector<int> answer = KMP(pattern, text); // answer 에 검색에 성공한 위치들이 담기게 된다.
	cout << answer.size() << '\n';
	for (int i = 0; i < answer.size(); ++i)
		cout << answer[i] << ' ';
}

🔥 두 번째 풀이 ⭕

#include <bits/stdc++.h>

using namespace std;

vector<int> Fail(string pattern) {
	int m = pattern.length();
	vector<int> pi(m); // partial match table

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

vector<int> KMP(string pattern, string text) {
	int m = pattern.length();
	int n = text.length();
	vector<int> pos;
	vector<int> pi = Fail(pattern);

	for (int i = 0, j = 0; i < n; i++) {
		while (j > 0 && text[i] != pattern[j])
			j = pi[j - 1];
		if (text[i] == pattern[j]) {
			if (j == m - 1) {
				pos.push_back(i - m + 1 + 1); // 위치를 1 부터 치기 때문에 +1 해줌
				j = pi[j];
			}
			else j++;
		}
	}
	return pos;
}

int main() {
	//freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	// 공백을 포함하는 문자열 입력
	string text;
	getline(cin, text);
	string pattern;
	getline(cin, pattern);

	vector<int> answer = KMP(pattern, text); // answer 에 검색에 성공한 위치들이 담기게 된다.
	cout << answer.size() << '\n';
	for (int i = 0; i < answer.size(); ++i)
		cout << answer[i] << ' ';
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기