백준 1786 찾기

찾기

문제 자체에서 KMP 알고리즘을 설명해주고 있다.
KMP 알고리즘에 접근하는 가장 기초적인 개념은 다음과 같다.
ABC/ABD/ABC/ABC/ABE/F(편의상 /는 Readability를 위해 표시했습니다)에서 ABCABE를 찾는다고 가정할 때,

A를 찾고, B를 찾고, … , D가 아니므로(C) A의 다음 자리인 B에서부터 처음부터 다시 찾는다.(이 방법은 브루트 포스 방법입니다. 사실 저는 이 방법밖에 떠오르지 않았습니다. 똑똑한 사람들..)
하지만 KMP 알고리즘은 이 앞의 ABCABE중에서 뒤의 AB와 앞의 AB가 같은 것을 이용한다.
ABC/ABD/ABC/ABC/ABE/F 에서 2번째 인덱스 부터가 아닌, 패턴이 같은 것을 이용해 6번째 인덱스인 D와 ABC/ABE중 C를 비교하는 것이다.
자세한 내용은 제가 참고했던 블로그를 보면 이해에 도움이 되겠습니다.(참고로 저는 이해하는데 두시간이 넘게 걸렸습니다… ㅠㅠ)

그리고 문제에 도움이 될 것 같은 팁.
문제는 공백을 포함해야하는데 공백을 포함한 문자열을 입력받는 방법은 다음과 같다.

string s;
getline(cin,s);

나는 답의 길이를 계속 저장해주었는데, j가 부분 문자열의 길이와 같을 때마다 답을 다른 배열에 저장해 주어도 좋을 것 같다.

오타나 질문, 지적 환영입니다.

소스

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
char office[9][9];
int n, m;
int i_index[4] = { -1,0,1,0 };
int j_index[4] = { 0, 1, 0, -1 };

vector<int> _fail(string p) {
	int m = p.size();
	vector<int> fail(m);
	fail[0] = 0;
	int j = 0;
	for (int i = 1; i < m; i++) {
		while (j > 0 && p[i] != p[j])
			j=fail[j - 1];
		if (p[i] == p[j])
			fail[i] = ++j;
		else
			fail[i] = 0;
	}
	return fail;
}



int main(){
	string t;
	string p;
	getline(cin, t);
	getline(cin, p);
	vector<int> fail;
	fail = _fail(p);
	int j = 0;
	int m = t.size();
	vector<int> answer(m);
	for (int i = 0; i < m; i++) {
		while (j > 0 && t[i] != p[j])
		{
			j = fail[j - 1];
		}
		if (t[i] == p[j])
			answer[i] = ++j;
		else
			answer[i] = 0;
	}
	int cnt = 0;
	for (int i = 0; i < m; i++)
	{
		if (answer[i] == p.size()) {
			cnt++;
		}
	}
	cout << cnt<<'\n';
	for (int i = 0; i < m; i++)
	{
		if (answer[i] == p.size())
			cout << i-p.size()+2 << ' ';
	}

}