어떤 문자열에서 특정 단어를 찾는 알고리즘은 굉장히 많이 존재한다.

  • Naive, 단순 이중 포문
  • KMP Algorithm : 이번에 익힐 접두 / 접미사를 이용한 알고리즘이다.
  • Rabin & Karp Algorithm : 해쉬를 이용한 알고리즘이다.
  • Boyer & Moore Algorithm : 굉장히 어려운 알고리즘이다.
  • Manber-Myers Algorithm : 접미사 배열을 이용한 알고리즘이다.

위 알고리즘들 중에서 이번에는 KMP 알고리즘을 완벽히 숙지해보려고 한다.

KMP?

KMP(Knuth, Morris, Prett) 알고리즘이란 무엇일까?

먼저 위에서 언급했듯이, 어떤 문자열에서 특정 단어를 찾으려면 얼마나 걸릴까?
길이 N의 문자열에서 길이 M의 단어를 찾는다고 생각해보자.
그럼 아래와 같이 코드를 작성해 볼 수 있을 것이다.

for (int i = 0; i < src.size() - dest.size(); i++) {
	for (int j = 0; j < dest.size(); j++) {
		if (src[i + j] != dest[j]){
			break;
      isSame = false;
    }
	}
  if(isSame)
     cout << "Same String! << "\n";
}

최악의 경우 N의 길이를 M만큼 매번 검사해야 하니, O(NM)의 시간복잡도가 발생한다.
이는 문자열의 길이가 길면 길수록 너무 많은 시간을 잡아먹는 알고리즘이다.

이런 문제점을 개선하기 위해 고안된 것이 바로 KMP 알고리즘!
접두사와 접미사의 개념을 통해 불필요한 탐색을 제외하고 탐색하는 알고리즘이다.
결론부터 말하자면, O(N+M)까지 시간 복잡도 개선이 가능한 알고리즘이다.

KMP 알고리즘의 구현

실패 함수

먼저 알아야 할 개념은 실패 함수 라는 개념이다.
실패 함수란 어떤 문자열의 접두, 접미사가 얼만큼 반복되는 지 기록하는 함수이며,
이름이 실패 인 이유는 불일치가 발생했을 때 동작하는 함수이기 때문이다.
이 개념이 시간 복잡도를 개선하기 위한 핵심 키워드가 된다.

아이디어는 다음과 같다.

image
위 사진과 같이 두 문자열을 비교해야하는 상황이 있다.
ABAA, 즉 4번째 칸에서 불일치가 발생을 했는데, 다음은 어떻게 검사할까?
한 칸만 옮겨서 BAAB와 검사한다면 원래의 naive한 방법과 동일하다.

비교 대상인 ABAB는 접두사 AB, 접미사 AB로 반복이 됨을 알 수 있는데,
이 점을 이용해서 우리는 굳이 반복되는 부분을 다시 검사할 필요가 없다.
일치하며 반복되는 AB를 넘어 AABA 부터 검사를 하면 된다.
이를 실제로 적용하기 위해 우리는 pi 배열 이라는 테이블을 필요료 한다.
이는 불일치가 발생했을 때, 얼마나 뛰어넘을 수 있는 지를 저장하는 테이블이다.
즉, 실패 함수의 개념은 pi 배열을 제작하는 함수라고 봐도 무방하다!

pi 배열(실패 배열)

백준 1786 : 찾기
image
위와 같은 문자열에 대해서 pi 배열을 만들어보자.

이를 코드로 작성하면 아래와 같다.

vector<int> make_pi(string target) {
	int cursor = 0;
	int size = target.size();
	vector<int> pi(size, 0);

	for (int i = 1; i < size; i++) {
		while (cursor > 0 && target[i] != target[cursor])
			cursor = pi[cursor - 1];
		if (target[i] == target[cursor]) {
			cursor++;
			pi[i] = cursor;
		}
	}

	return pi;
}

위의 코드를 진행하고 나면 아래와 같은 pi 배열이 만들어지게 된다.
image
이제 아래 단계에서 pi 배열을 실제로 적용하는 방법을 알아보자.

실제 KMP로의 적용

실제로 KMP 알고리즘도, 실패 함수와 동일한 원리로 작동한다.
아래의 코드는 위에서 언급했던 백준 : 찾기 문제의 코드이다.
pi 배열 생성 코드는 위에 있으며, KMP 부분만 따로 떼놓은 코드이다.

void kmp(string src, string target) {
	vector<int> pi = make_pi(target);
	int cursor = 0; // 동일하게 커서 사용
	int src_size = src.size(), target_size = target.size();

	for (int i = 0; i < src_size; i++) {
		while (cursor > 0 && src[i] != target[cursor]) // 비교 대상이 자신이 아닌 문자열이다.
			cursor = pi[cursor - 1]; // 다르면 실패한 부분에서 겹치는 문자열 길이만큼 점프
		if (src[i] == target[cursor]) { // 같으면
			if (cursor == target_size - 1) { // 완전히 같은 문자열인 경우
				answer.push_back(i - target_size + 1); // 답에 위치 저장
				cursor = pi[cursor]; // 현재 문자열의 길이만큼 점프
			}
			else
				cursor++; // 커서를 뒤로 옮김
		}
	}
}

이론적으로만 알고 적용하기엔 매우 복잡한 알고리즘이었다.
KMP나 위상정렬 같은 고급 알고리즘은 실제로 적용해보는 것이 중요하다.