[백준] 1786번 찾기

문제: 1786번: 찾기

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string T;
	getline(cin, T);

	string p;
	getline(cin, p);

	// 문제에서 특정 조건이 없다면 KMP 문제를 풀 때, 연속적으로 겹쳐지는 패턴도 각각 카운팅 해야한다고 함..

	// 첫째 줄에, T 중간에 P 가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다.
	// 둘째 줄에는 P 가 나타나는 위치를 차례대로 공백으로 구분해 출력한다.
	int n = T.size();
	int m = p.size();

	// pi 배열 구해야함(문자가 일치하지 않을 때 어디로 점프해야 하는지 정보 저장)
	// 겹치는 것도 세는 경우니까 pi 배열의 크기를 m 만큼..
	vector<int> pi(m + 1); // p 의 사이즈만큼
	int i = 1;
	int j = 0;
	// 겹치는 것도 세는 경우니까 pi 배열의 m-1 번도 돌아갈 곳 지정해줘야함..
	while (i < m) {
		// 문자가 같을 때
		if (p[j] == p[i]) {
			i++;
			j++;
			pi[i] = j; // 돌아갈 위치 저장
		}
		// 문자가 다르고 j 가 0일 때
		else if (j == 0) {
			i++;
			pi[i] = j; // 돌아갈 위치(이 경우는 0 임)
		}
		// 문자가 다르고 j 가 0 이 아닐 때
		else {
			j = pi[j]; // 저장해 놓은 위치로 점프
		}
	}

	// i 가 T 의 사이즈보다 작을 때까지 반복
	i = 0;
	j = 0;
	int cnt = 0; // T 에 존재하는 p 의 개수
	queue<int> pos;
	while (i < n) {
		if (p[j] == T[i]) {
			i++;
			j++;

			// 단어를 찾았으면 다시 돌아가기
			if (j == m) {
				cnt++;
				pos.push(i - j);
				j = pi[j]; // 저장해놓은 곳으로 돌아가기..
			}
		}
		else if (j == 0) {
			i++;
		}
		else {
			j = pi[j]; // 저장해 놓은 위치로 점프
		}
	}
	cout << cnt << "\n";
	while (!pos.empty()) {
		int num = pos.front();
		pos.pop();
		cout << num + 1 << " "; // 주어진 문제 상에서는 인덱스가 1부터 시작하니까 +1 해주기
	}


	return 0;
}

 

KMP 알고리즘을 이용하는 문제에서는 특정 조건이 없으면 연속적으로 겹치는 패턴도 각각 cnt 에 반영해야 한다고 한다.

 

그래서 강의안으로 공부했던 거에서 내용이 살짝 달라지는데 대표적으로는 pi 벡터의 크기가 m+1 만큼이 되어야 한다던지(pi 는 원래 LPS 길이 배열을 한 칸 옮긴거라 m 만큼의 크기를 잡았었는데 여기에서 맨 마지막 문자가 돌아가야 하는 위치까지 저장해야 하므로 m+1 만큼의 크기로 설정해준 것이다.)

 

즉, p 의 j 번 요소가 T 의 i 번 요소와 다르면 pi[j] 값으로 j 값을 재설정한 후 계속해서 반복문 돌면서 판단하면 된다. 

 

또 달라진 점은 패턴을 찾은 다음에 j 를 어느값으로 바꿔줘야 하는가였는데, 연속적으로 겹치는 패턴을 세지 않는 경우에는 그냥 j 의 값을 0 으로 설정해주면 되지만 허용하는 경우에는 j 의 값을 pi[j] 값으로 설정해줘야 하는 것이었다.

 

아.. 내용을 이해한 것 같으면서도 막상 설명하라고 하면 제대로 못하겠는 거 보니까 한참 부족한 것 같다.. 내일도 복습하면 괜찮아지겠지. 뭐든지 처음 보는건 어려우니까 너무 상심하지 말고 계속 복습하자!!! 파이팅 ^0^   

 

 

 

참고자료:

KMP : 문자열 검색 알고리즘 - 멍멍멍

KMP : 문자열 검색 알고리즘