[C/C++] 백준 1786번 - 찾기

✏️문제 링크

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

1786번: 찾기

 

✏️문제 설명

 

 

✏️문제 풀이

문제의 설명이 상당히 길게 나와 있는데 사실 저 말들은 모두 KMP알고리즘의 실패함수 처리 부분과

KMP알고리즘을 구현하는 방법에 대한 설명을 말로 풀어논 것입니다.

따라서 KMP알고리즘을 시행해서 몇 번 나타나는지, 그리고 어디서 일치하는지를 출력하면 됩니다.

https://pooreumjung.tistory.com/358

Algorithm 공부 #27 - KMP(Knuth–morris–pratt)

 

✏️문제 코드

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

void KMP(string parent, string pattern);
vector<int>makeFailTable(string pattern);
vector<int>res;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string pattern, parent;
	getline(cin, parent);
	getline(cin, pattern);

	KMP(parent, pattern);
	cout << res.size() << '\n';
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << "\n";
}
void KMP(string parent, string pattern) {
	vector<int>table = makeFailTable(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) {
				res.push_back(i - patternSize + 2);
				j = table[j];
			}
			else
				j++;
		}
	}

}

vector<int> makeFailTable(string pattern)
{
	int patternSize = pattern.size();
	int j = 0;
	vector<int>failTable(patternSize, 0);

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