KMP 알고리즘

KMP 알고리즘은 문자열 안에서 주어진 문자열을 찾는 알고리즘으로 O(nm)을 O(n+m)으로 개선시킬 수 있다.

prefix, suffix

apple로 예를 들어 본다.

• prefix는 a, ap, app, appl, apple가 된다.
• suffix는 e, le, ple, pple, apple가 된다.

pi 배열

ABAABAB를 예로 들어본다.

• pi[0]은 A이므로 0이다.
• pi[1]은 AB이므로 0이다.
• pi[2]는 ABA이므로 1이다. (A)
• pi[3]은 ABAA이므로 1이다. (A)
• pi[4]는 ABAAB이므로 2이다. (AB)
• pi[5]는 ABAABA이므로 3이다. (ABA)
• pi[6]은 ABAABAB이므로 2이다. (AB)

KMP 알고리즘

KMP 알고지름은 문자열을 검사할 때 중복된 부분으로 건너 뛰어 검사를 할 수 있다. 이때 pi 배열이 사용된다.

• ABCDABCDABEE라는 문자열에서 ABCDABE라는 문자열을 찾는다고 가정한다.
• 처음 검사시에 ABCDAB까지는 같지만 뒤에 C와 E가 다르게 된다.
• 이때 KMP 알고리즘은 다음 한칸을 이동해서 검사를 하는 것이 아니라 pi 배열을 확인하여 그 위치로 바로 이동해 다시 검사를 진행한다.
• KMP 알고리즘을 사용하지 않는다면 5번만에 찾게 되지만, KMP 알고리즘을 사용하면 2번만에 찾게 된다.

Code

#include <iostream>

#define MAX_STRING 1000000
#define MAX_WORD 1000

using namespace std;

char S[MAX_STRING + 1];
char W[MAX_WORD + 1];
int fail[MAX_WORD];
int result[MAX_WORD];
int N, M, R;

void getFailFunc() {
	M = 0;
	while (W[M]) M++;

	for (int i = 1, j = 0; i < M; i++) {
		while (j > 0 && W[i] != W[j]) j = fail[j - 1];

		if (W[i] == W[j]) {
			fail[i] = ++j;
		} else {
			fail[i] = 0;
		}
	}
}

void KMP() {
	getFailFunc();
	N = 0, R = 0;
	for (int i = 0; i < MAX_WORD; i++) result[i] = 0;
	while (S[N]) N++;

	for (int i = 1, j = 0; i < N; i++) {
		while (j > 0 && S[i] != W[j]) j = fail[j - 1];

		if (S[i] == W[j]) {
			if (j == M - 1) {
				result[R++] = i - M + 1;
				j = fail[j];
			}
			else j++;
		}
		else j = 0;
	}
}

int m_strcmp(const char* str1, const char* str2) {
	int i = 0, j = 0;

	while (str1[i] != '\0' || str2[j] != '\0') {
		if (str1[i] != str2[j]) return str1[i] - str2[j];
		else {
			i++; j++;
		}
	}

	return 0;
}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> S;
	
	while (true) {
		cin >> W;
		if (!m_strcmp(W, "q")) break;

		KMP();
		if (R == 0) cout << W << " 는 없는 단어입니다.\n";
		else
			for (int i = 0; i < R; i++) {
				cout << result[i] + 1 << "번째 위치에서 발견하였습니다.\n";
			}
	}

	return 0;
}