PS/백준 문제 풀이

백준 1786번 - 찾기(C++)

홀든콜필드 2024. 1. 26. 12:47
728x90

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

 

1786번: 찾기

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m

www.acmicpc.net

 

KMP 알고리즘의 기본 문제이다. 문제에서도 친절하게 KMP알고리즘에 대해 설명하고 있다.

 

https://tigerfrom2.tistory.com/400

 

문자열 찾기 - KMP 알고리즘

KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한

tigerfrom2.tistory.com

 

위 포스팅에 KMP알고리즘에 대해 설명해놓았으니 참고하면 좋다. 

이 문제는 getline 만 조심하면 KMP알고리즘을 그대로 사용할 수 있다.

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

int cnt = 0;
vector<int> idx;

vector<int> createTable(string target) {
	int N = target.size();
	vector<int> table(N, 0);
	int j = 0;
	for (int i = 1; i < N; i++) {
		while (j > 0 && target[i] != target[j]) {
			j = table[j - 1];
		}

		if (target[i] == target[j]) {
			table[i] = ++j;
		}
	}

	return table;
}

void KMP(string input, string target, vector<int>& table) {
	int j = 0;
	for (int i = 0; i < input.size(); i++) {
		while (j > 0 && input[i] != target[j]) {
			j = table[j - 1];
		}

		if (input[i] == target[j]) {
			if (j == target.size() - 1) {
				cnt++;
				idx.push_back(i - target.size() + 2);

				j = table[j];
			}
			else {
				j++;
			}
		}
	}
}

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

	string input;	
	string target;

	getline(cin, input);
	getline(cin, target);

	vector<int> table = createTable(target);
	KMP(input, target, table);
	
	cout << cnt << '\n';

	for (int id : idx) cout << id << ' ';
}