백준 1786 - 찾기

백준 1786-찾기는 문자열 모음에서 하나의 문자열이 몇번 등장하는지 찾는 문제이다. KMP 기본문제라서 KMP를 공부하고나서 쉽게 풀었다. 사실 KMP만 알면 누구나 풀 수 있는 문제이다. 

 

찾았을 때 begin+1을 한 이유는 문자열을 탐색할 때 index는 0부터 시작하지만 문제입장에서는 1번째 문자 부터 검사하기 때문이다.

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

vector<int> getPi(string hook);
vector<int> KMPSEARCH(string base, string hook);


int main(){
	string base, hook;
	getline(cin, base);
	getline(cin, hook);

	vector<int> result = KMPSEARCH(base, hook);
	printf("%d\n", result.size());
	for(auto ret : result)
		printf("%d\n", ret);
}

vector<int> getPi(string hook){
	int hookSize = hook.size();
	vector<int> pi(hookSize, 0);

	int begin = 1, matched = 0;

	while(begin + matched <= hookSize){
		if(hook[begin + matched] == hook[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> KMPSEARCH(string base, string hook){
	int begin = 0, matched = 0;
	vector <int> pi = getPi(hook);
	vector<int> result;
	int baseSize = base.size(), hookSize = hook.size();

	while(begin <= baseSize - hookSize){
		if(base[begin + matched] == hook[matched]){
			matched++;
			if(matched == hookSize) result.push_back(begin+1);
		}else{
			if(matched == 0)
				begin++;
			else{
				begin+=matched - pi[matched-1];
				matched = pi[matched-1];
			}
		}
	}

	return result;
}