백준 1786 : 찾기

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

1786번: 찾기

 

KMP 그 자체인 문제다. 문제 설명에서도 KMP 알고리즘의 로직을 설명하고있다.

 

+) KMP 알고리즘 참고 자료

https://injae-kim.github.io/dev/2020/07/23/all-about-kmp-algorithm.html

Injae's devlog

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string p, t;

//pi 배열 업데이트
vector<int> getPi() {
	//1번 인덱스부터 검사
	int idx = 1, matched = 0;
	vector<int> pi(p.size(), 0);

	while (idx + matched < p.size()) {
		//일치한다면 matched 증가 및 pi배열 갱신
		if (p[idx + matched] == p[matched]) {
			++matched;
			pi[idx + matched - 1] = matched;
		}
		//일치하지 않는다면
		else {
			//하나도 일치하는게 없으면 단순히 시작 인덱스 증가
			if (!matched) ++idx;
			//일치하는 데이터가 있을 시 이미 확인된 공통 접두,접미사
			//길이만큼 이동
			else {
				idx += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}

//src 문자열과 pattern 문자열 비교
//방법은 pi 배열 업데이트 방법과 동일
vector<int> kmp() {
	int idx = 0, matched = 0;
	vector<int> ret;
	vector<int> pi = getPi();

	while (idx + matched < t.size()) {
		if (matched < p.size() &&
			t[idx + matched] == p[matched]) {
			++matched;
			//매칭된 개수가 패턴 문자열의 길이와 같을 시
			//정답 배열에 시작 인덱스 추가
			if (matched >= p.size())
				ret.push_back(idx);
		}
		else {
			if (!matched) ++idx;
			else {
				idx += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return ret;
}

void solution() {
	getline(cin, t);
	getline(cin, p);

	vector<int> ans = kmp();
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] + 1 << ' ';
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 9432 kb

시간: 60 ms

 

KMP는 발상 자체는 간단한 것 같으면서도 구현 방법을 보면 이게 이렇게 구현된다는게 신기하다는 생각이 든다.