1786 찾기

KMP 기본문제로 패턴에 대한 실패 배열을 만들어서, 이를 이용해 중복 검사를 피할 수 있다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/1786.cpp

 

	#include <cstdio>
	#include <string>
	#include <vector>
	#include <sstream>
	#include <iostream>
	using namespace std;
	vector<int> makeTable(string pattern) {
	int strsize = pattern.size();
	vector<int> table(strsize);
	int j = 0;
	for(int i=1; i<strsize; 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) {
	int prsize = parent.size();
	int ptsize = pattern.size();
	int j = 0;
	vector<int> table = makeTable(pattern);
	vector<int> ans;
	for(int i=0; i<prsize; i++) {
	while(j > 0 && parent[i] != pattern[j]) {
	j = table[j-1];
	}
	if(parent[i] == pattern[j]) {
	if(j == ptsize-1) {
	ans.push_back(i-ptsize+2);
	j = table[j];
	}
	else {
	j++;
	}
	}
	}
	cout << ans.size() << '\n';
	for(int i=0; i<ans.size(); i++) {
	cout << ans[i] << '\n';
	}
	}
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string parent, pattern;
	getline(cin, parent);
	getline(cin, pattern);
	KMP(parent, pattern);
	return 0;
	}

view raw 1786.cpp hosted with ❤ by GitHub