상경한 개발자 지망생들

문제 링크

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

접근 방법

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

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

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

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

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