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

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

1786번: 찾기

 

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

 

https://tigerfrom2.tistory.com/400

문자열 찾기 - KMP 알고리즘

 

위 포스팅에 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 << ' ';
}