문자열 찾기 - KMP 알고리즘

KMP 알고리즘이란?

KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다.

KMP의 아이디어

KMP의 중요한 아이디어는 접미사와 접두사이다.

접미사와 접두사는 단어를 반으로 잘라 왼쪽이 접두사 오른쪽이 접미사가 된다.

ABCDAB 가 있으면 ABC는 접두사 DEF는 접미사가 된다.

자, 이걸 어떻게 쓸 수 있을까. 위 단어는 접두사와 접미사가 일치하는 것이 없다. 그러니 다른 예제를 보자. ABA 라고 생각하자. 접두사와 접미사에 모두 A가 있다.

그리고 ABAABA 라는 인풋에서 ABA를 찾는다고 생각해보자.

ABAABA

ABA

1개를 찾았다. 원래같으면

ABAABA

ABA

ABA

이런식으로 슬라이딩 윈도우처럼 이동했을 것이다. 하지만, 접두사 접미사 개념을 사용하면 여기서

ABAABA

ABA

ABA

이렇게 바로 이동 시킨다. 위의 경우보다 1번의 연산이 더 적다. 많은 차이가 안나 보이지만 문자열의 길이가 늘어나면 아주 유의미한 차이를 보이게 된다.

그러므로 중요한 것은 타겟 문자열이 같은 문자열 갯수가 몇개인가? 에 대해 몇 번을 한번에 밀어줄 수 있는가? 하는 테이블을 만들어줘야한다.

접두, 접미 Table 만들기

ABACAABA 를 예시로 들어보자.

0 → 0

A → 0

AB → 0

ABA → 1

ABAC → 0

ABACA → 1

ABACAA → 1

ABACAAB → 2

ABACAABA → 3

이 숫자들을 테이블로 만들어두고 각 자리수대로 일치한다면 다음으로 1씩 올리는 것이 아니라 위의 자리수로 가게 된다.

그렇다면 위의 테이블은 어떻게 만들어질까?

vector<int> create_failTable(string target) {
	int n = target.size();
	vector<int> table(n, 0);
	
	table[0] = 0;

	int i = 1;
	int j = 0;

	for (i = 1; i < n; i++) {
		while (j > 0 && target[i] != target[j]) {
			j = table[j - 1];
		}
		if (target[i] == target[j]) {
			j += 1;
			table[i] = j;
		}
	}

	return table;
}

여기서 가장 중요한 코드는

while (j > 0 && target[i] != target[j]) {
			j = table[j - 1];
		}

이곳이다. 이것이 KMP의 핵심이다. 이 코드는 접두 접미가 다른 곳을 찾았을 때, 접두 접미가 같은 곳까지만 내려가서 다시 탐색하겠다는 의미이다. 리니어하게 모든 것을 보지 않아도되도록 하는 가장 중요한 코드조각이다.

int KMP(string input, string target, vector<int>& table) {
	int n = input.size();
	int m = target.size();

	int i = 0;
	int j = 0;
	int answer = 0;
	while (i < n) {
		while (j > 0 && input[i] != target[j])
			j = table[j - 1];
		if (input[i] == target[j]) {
			if (j == m - 1) {
				answer++;
				j = table[j];
			}
			else j++;
		}
		i++;
	}

	return answer;
}

KMP는 다음과 같다. 테이블을 만드는 것과 비슷하다.

i는 인풋의 인덱스를 맡고 j는 타겟의 인덱스를 맡는다.

i는 계속 1씩 증가하게되고 j는 최대한 접두 접미에 맞게 갱신된다. 이러면 최악의 경우는 O(N * M) 이지만 M이 접두 접미사가 있을 경우 최적화되기 때문에 시간을 많이 절약할 수 있다.