[알고리즘] KMP 알고리즘 - 빠른 문자열 찾기 (C++로 구현하기)

KMP 알고리즘이란?

'Knuth-Morris-Pratt' 의 줄임말입니다. 이 알고리즘을 설계한 사람들입니다.

전체 문자열에서, 특정 문자열(패턴)을 빠르게 찾는 알고리즘입니다.

이와 비슷하게 문자열을 찾는 여러 알고리즘이 있습니다.

대략적으로 소개하자면 다음과 같습니다.

 

- Naive Algorithm : 가장 쉽게 생각할 수 있는, O(N²)의 전체 탐색 알고리즘입니다.

- Rabin & Karp Algorithm : 해시를 이용한 문자열 탐색 알고리즘입니다.

- Boyer & Moore Algorithm : 일반적으로 가장 빠른 알고리즘입니다.

- Suffix Tree / Array : 접미사 트리 / 배열이라고 불리는, 테이블을 이용한 알고리즘입니다.

 

KMP 알고리즘 역시 이해하기 어렵습니다.

실제로 대부분의 분들이 한번에 이해하지 못합니다.

하지만 구현하는 방법을 잘 익혀두면 PS에 분명히 도움이 되니 알아두는 것이 좋겠습니다.

 

 

 

동작 원리

KMP 알고리즘을 '빠르게' 문자열(패턴)을 찾는 알고리즘이라고 했습니다.

바꿔 말하면, 효율적으로 찾는다는 것입니다.

가장 기본적으로 생각할 수 있는 O(N²) 알고리즘이 왜 느릴까요?

문자 하나하나를 다 검색하기 때문에 효율이 저하되기 때문입니다.

이를 극복하기 위해, KMP 알고리즘에서는 실패함수 (Fail function) 라는 개념을 도입했습니다.

 

이 실패함수는,

'문자 매칭에 실패했을 때, 얼만큼 건너뛰어야 하는가?'를 알기 위해 사용됩니다. 

다른 말로는,

'문자 매칭에 실패하기 직전 상황에서, 접두사 / 접미사가 일치한 최대 길이'라고 풀이됩니다.

 

다음과 같은 상황을 보겠습니다.

 

전체 문자열 'ababdababa' 에서, 

패턴 문자열 'ababa' 를 찾으려고 합니다.

찾는 과정에서, 위의 그림과 같이 5번째 문자에서 불일치가 발생했습니다.

 

만약 모든 문자를 대상으로 찾는 알고리즘이라면 한 칸을 이동하겠지만,

KMP 알고리즘은 실패함수를 기반으로 아래와 같이 이동하겠다는 것입니다.

 

 

어떻게 이러한 것이 가능할까요?

바로, 불일치가 발생한 부분에서 직전까지 일치했던 최대 접두사 / 접미사가 'ab' 였기 때문입니다.

여기에서 최대 접두사 / 접미사라는 것은 본인 전체는 제외하기 때문에, 'abab'가 아닌 'ab'인 것입니다.

 

 

 

 

실패함수의 구현

'ababc'를 기준으로 실패함수를 구해보겠습니다.

2개의 인덱스 (i, j) 를 활용해서 실패함수를 구할 것입니다.

인덱스를 증가시켜나가며 두 문자가 일치하면 두 인덱스를 증가시키고,

일치하지 않으면 이전까지의 상황의 실패함수를 참고해나가며, 참고할 값이 없으면 0 이 됩니다.

말로는 이해가 어려우니 아래의 예시를 보겠습니다.

 

실패함수의 첫번째 항목은 0 입니다.

위에서 자기 자신은 제외한다고 했으므로 항상 0 으로 생각하시면 됩니다.

현재 i 와 j 인덱스에서 문자가 불일치하므로, 이전까지의 실패함수를 참고를 시도합니다.

하지만 이전 상태에서의 실패함수의 값은 0 입니다.

그러므로, i 번째 Fail 함수의 값도 다음과 같이 0 으로 갱신되고, i 가 증가합니다.

 

이번엔 어떤가요?

i 와 j 에서 문자열이 일치하므로, 다음과 같이 j + 1의 값이 i번째 실패함수의 값으로 입력되며,

i와 j의 값이 모두 증가합니다.

 

여기에서도 역시, 'b' 와 'b' 로 일치하기 때문에

i 번째 실패함수의 값은 j + 1인 2로 변경됩니다.

 

이제는 어떤가요?

'b'와 'c'로 불일치하기 때문에, 이전까지의 실패함수를 참고합니다.

자세하게는, 이전 인덱스의 실패함수의 값으로 j를 옮겨서, 다시 문자를 비교합니다.

지속해서 불일치한다면 j가 0이 될 때까지 반복합니다.

 

최종적으로 위와 같은 실패함수가 만들어졌습니다.

이 실패함수로 알수 있는 사실은 다음과 같습니다.

 

- 'a' 까지 일치하는 접두사/접미사 최대 길이 : 0 (없음) 

- 'ab' 까지 일치하는 접두사/접미사 최대 길이 : 0 (없음)

- 'aba' 까지 일치하는 접두사/접미사 최대 길이 : 1 ('a')

- 'abab' 까지 일치하는 접두사/접미사 최대 길이 : 2 ('ab')

- 'ababc' 까지 일치하는 접두사/접미사 최대 길이 : 0 (없음)

 

이러한 사실을 이용해서, KMP 알고리즘을 구현할 수 있습니다.

 

 

 

KMP 알고리즘의 동작 원리

아래와 같은 상황을 가정해보겠습니다.

전체 문자열은 'ababdababc' 이고,

찾는 문자열은 'ababc' 입니다.

 

5번째 항목에서 불일치가 발생했습니다.

그러므로, 우리는 4번째의 실패함수 값을 참조합니다.

 

'abab' 까지는 실패함수가 2 라는 값임을 보여줍니다.

이 값이 무슨 값인지 기억하시나요?

'abab' 에서는 'ab'로 최대 접두사/접미사 길이가 2 라는 것입니다.

그러므로 이 값을 참고해서, 우리는 2 만큼 패턴을 이동할 수 있게 됩니다.

 

이번엔 어떤가요?

6번째 항목에서 불일치가 발생했습니다.

위와 동일하게, 3번째의 실패함수 값을 참고하면 1 만큼 이동할 수 있겠습니다.

 

역시 동일하게, 이 상황에서는 4번째 실패함수의 값을 참고합니다.

2 칸을 이동합니다.

 

드디어 원하는 패턴을 찾았습니다.

 

 

 

구현 (C++)

#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;
}