[백준] 1786번 찾기 (KMP 알고리즘)

• KMP 알고리즘에 대한 공부를 끝마치고 문제를 풀기 위해 찾아봤더니 바로 적용할 수 있는 문제가 있었다.

---

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

1786번: 찾기

• KMP 알고리즘만 알고 있다면 별로 어렵지 않게 풀 수 있었다.
• 처음 풀때 시간초과가 났는데 endl --> "\n" 을 해주어야 시간초과가 나지 않는다..

---

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>

using namespace std;
vector<int> answer;
int countt;
vector<int> makeTable(string pattern) {
	int patternSize = pattern.length();
	vector<int> table(patternSize, 0);
	int j = 0;
	for (int i = 1; i < patternSize; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j]) {
			table[i] = ++j;
		}
	}
	return table;
}

void KMP(string parent, string pattern) {
	vector<int> table = makeTable(pattern);
	int parentSize = parent.size();
	int patternSize = pattern.size();
	int j = 0;
	for (int i = 0; i < parentSize; i++) {
		while (j > 0 && parent[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (parent[i] == pattern[j]) {
			if (j == patternSize - 1) {
				countt++;
				answer.push_back(i - patternSize + 2);
				//printf_s("%d", i - patternSize + 2);
				j = table[j];
			}
			else {
				j++;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string parent, pattern;
	countt = 0;
	getline(cin, parent);
	getline(cin, pattern);

	KMP(parent, pattern);

	cout << countt << "\n";
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << "\n";
	}

	return 0;
}