[C++] 백준 1786 찾기 (KMP 알고리즘)

문제 링크

---

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

1786번: 찾기

 

접근 방법

---

문자열 검색 알고리즘인 KMP 알고리즘의 구현을 묻는 문제였습니다.

일반적인 문자 Character by Character mapping은 두 문자열의 길이의 곱인 O(NM)만큼 연산을 하게 됩니다.

KMP 알고리즘은 O(N + M)만큼의 시간만에 검색 연산을 해낼 수 있습니다.

 

KMP 알고리즘은 문자열이 모든 부분 일치하지 않더라도 현재까지 일치했던 영역 내에서의 정보를 최대한 활용합니다.

주로 활용하는 정보는 일치하는 영역 내의 '문자열 내 접두와 접미의 반복'이 있는가? 입니다. 반복이 없으면 일치하는 영역 내에 재검사할 정보가 없기때문에 일치하는 만큼 건너 뛰고, 반복이 있다면 반복하는 영역으로 점프하여 검사하는 것이 기본 아이디어입니다.

j=3에서 틀렸다. 일치하는 영역 내에 접두/접미의 반복이 없으므로 i=3을 유지한 채로 j=0으로 변경(점프)한다.

점프하였지만 j=0에서 불일치 -> 활용할 정보가 없으므로 i++

 

아래의 사진을 보면 이해하기 쉽습니다.

ABCDAB에서 접두/접미 AB가 반복되므로 반복되는 문자열의 길이 j = k = 2부터 다시 비교하는 KMP 알고리즘

KMP 알고리즘은 위와 같이 일치하는 문자열 내에 정보를 최대한 활용함으로써 O(N + M)의 시간복잡도로 문자열 검색을 구현할 수 있습니다.

 

패턴 문자열 P의 문자열 길이 1 ~ P.length()까지 접두/접미의 길이 k를 미리 계산해놓고 j를 얼마나 이동할지를 결정하는 것이 KMP 알고리즘의 핵심입니다.

 

ABCABD의 경우,

A, k = 0

AB, k = 0

ABC, k = 0

ABCA, k = 1

ABCAB, k = 2

ABCABD, k = 0 이 되겠습니다.

 

소스 코드

---

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
string S, P;

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

void solve() {
	int cnt = 0;
	vector<int> cd;
	vector<int> k = get_failure(P);
	for (int i = 0, j = 0; i < S.size(); ++i) {
		while (j > 0 && S[i] != P[j])
			j = k[j - 1];
		if (S[i] == P[j]) {
			if (j + 1 == P.size()) {
				++cnt;
				cd.push_back(i - j + 1);
				j = k[j];
			}
			else {
				++j;
			}
		}
	}

	cout << cnt << "\n";
	for (int i = 0; i < cd.size(); ++i) {
		cout << cd[i] << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	getline(cin, S); getline(cin, P);
	solve();
	return 0;
}

개발 환경 : Visual Studio 2019

질문, 덧글, 지적 환영합니다.