[문자열] KMP Algorithm

작성일 | In

KMP 알고리즘의 이름은 제작자인 Knuth, Morris, Prett의 앞 글자를 따서 만들어졌습니다.

prefix와 suffix

KMP 알고리즘을 알아보기 전에, prefix(접두사)와 suffix(접미사)를 먼저 알아봅시다.
접두사는 맨 앞부터 특정 지점까지 연속된 문자열이고, 접미사는 맨 뒤부터 특정 지점까지 연속된 문자열입니다.
ABCABDAB 에서 접두사들은 아래와 같이 8개가 있습니다.

  1. A
  2. AB
  3. ABC
  4. ABCA
  5. ABCAB
  6. ABCABD
  7. ABCABDA
  8. ABCABDAB

접미사들은 아래 8개입니다.

  1. B
  2. AB
  3. DAB
  4. BDAB
  5. ABDAB
  6. CABDAB
  7. BCABDAB
  8. ABCABDAB

prefix와 suffix는 아래와 같이 간단하게 구할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<string> get_prefix(string str){
	int n = str.size();
	vector<string> prefix;

	string tmp = ""; tmp += str[0];
	prefix.push_back(tmp);
	for(int i=1; i<n; i++){
		prefix.push_back(prefix.back() + str[i]);
	}
	return prefix;
}

vector<string> get_suffix(string str){
	int n = str.size();
	vector<string> suffix;

	string tmp = ""; tmp += str.back();
	suffix.push_back(tmp);
	for(int i=n-2; i>=0; i--){
		suffix.push_back(str[i] + suffix.back());
	}

	return suffix;
}

pi배열이란?

KMP 알고리즘은 흔히 pi라고 불리는 배열을 이용해서 문자열을 검색합니다.
pi[i] = P의 i까지 부분 문자열에서 prefix==suffix가 될 수 있는 부분 문자열 중 가장 긴 것의 길이 로 정의됩니다. 단, prefix가 i까지의 부분 문자열과 같으면 안됩니다.
ABCABDAB 를 예시로 pi배열을 만들어 봅시다.

  1. A -> 0
  2. AB -> 0
  3. ABC -> 0
  4. A BC A -> 1
  5. AB C AB -> 2
  6. ABCABD -> 0
  7. A BCABD A -> 1
  8. AB CABD AB -> 2

한 가지 예제만 더 보고 넘어갑시다. ABACABABAC 로 pi배열을 만들어봅시다.

  1. A -> 0
  2. AB -> 0
  3. A B A -> 1
  4. ABAC -> 0
  5. A BAC A -> 1
  6. AB AC AB -> 2
  7. ABA C ABA -> 3
  8. AB ACAB AB -> 2
  9. ABA CAB ABA -> 3
  10. ABAC AB ABAC -> 4

pi배열 구하기

prefix와 suffix를 모두 알아보았고, 그것을 이용한 pi배열이 무엇인지 알아보았으니 pi배열을 구해봅시다.

Naive한 방법은 각 substring마다 prefix와 suffix를 구한 뒤, 비교하는 방법이 있습니다. O(P2)이 걸립니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> get_pi(string str){
	int n = str.size();
	vector<int> pi(n, 0);
	vector<string> substring = get_prefix(str);

	pi[0] = 0;
	for(int i=1; i<n; i++){
		vector<string> prefix = get_prefix(substring[i]);
		vector<string> suffix = get_suffix(substring[i]);

		for(int j=prefix.size()-2; j>=0; j--){
			if(prefix[j] == suffix[j]){
				pi[i] = prefix[j].size();
				break;
			}
		}
	}

	return pi;
}

이런 방식이 최적일리가 없으니 최적화를 시켜봅시다.

ABACABABAC 를 봅시다.

  1. pi[0]은 A만 보기 때문에 당연히 0이 나옵니다.
  2. pi[1]는 AB를 봅니다. 0이 나오게 됩니다.
  3. pi[2]는 ABA를 봅시다. ABA에서 A가 공통이기 때문에 1이 나옵니다.
  4. pi[3]은 ABAC를 봅니다. pi[3-1], 즉 pi[2]가 1이라는 것은 0~2 범위인 ABA에서 두 A가 같다는 것을 의미합니다. pi[3]을 구하기 위해서는 뒤에 C를 추가해야 합니다. 이미 A끼리는 같으니 prefix 뒤에 있는 B와 새로 추가되는 C를 비교해봅시다. 만약 같다면 pi[3]은 2가 됩니다. 하지만 다르므로 0이 들어가게 됩니다.
  5. pi[4]는 ABACA를 봅니다. 맨 앞에 있는 A와 맨 뒤에 있는 A가 같으므로 1을 넣어줍시다.
  6. pi[5]는 ABACAB를 봅니다. pi[5-1]을 보니 1이 저장되어 있습니다. 이 말은 맨 앞에 있는 글자 1개와 맨 뒤에 있는 글자 1개가 같다는 의미입니다. prefix 뒤에 있는 B와 새로 추가되는 글자 B가 같으므로 pi[5] = pi[5-1] + 1이 됩니다.
  7. pi[6]은 ABACABA를 봅니다. pi[6-1]을 보니 2가 저장되어 있습니다. prefix 뒤에 있는 A와 새로 추가되는 글자 A가 같으므로 pi[6] = pi[6-1] + 1이 됩니다.
  8. pi[7]은 ABACABAB를 봅니다. pi[7-1]을 보니 3이 저장되어 있네요. prefix 뒤에 있는 C와 새로 추가되는 글자 B가 다르기 때문에 0을 저장해야 할까요? 정답은 아닙니다.
    pi[6]이 3이라는 것은 앞에 3글자인 ABA 가 공통이라는 것을 의미합니다. p[3]을 봅시다. 1이 저장되어있네요. 이것은 ABACABA 에서ABA C ABA 굵은 글씨로 표현된 A가 모두 공통이라는 것을 의미합니다. 길이가 3인 것도 공통이지만, 1인 것도 공통이기 때문에 두 번째 글자인 B와 새로 추가되는 글자인 B를 비교합시다. 같으므로 pi[7] = 2가 되네요.
  9. pi[8]은 계산을 해보면 pi[7] + 1이 됩니다.
  10. pi[9]는 계산을 해보면 pi[8] + 1이 됩니다.

코드로 구현을 해봅시다.
일단 pi[0] = 0인 것은 자명합니다.
변수 몇 개를 정의해봅시다. i는 0~i 범위의 부분 문자열의 맨 뒤 인덱스, j는 prefix와 suffix가 같을 때의 prefix의 맨 뒤 인덱스라고 정의를 합시다.
p[i]와 p[j]가 같다면, 위에 있는 예제에서 pi[6]을 구하는 과정과 같습니다. 그런 경우에는 pi[i] = j+1이 됩니다.
반대로, p[i]와 p[j]가 다른 경우는 pi[7]을 구할 때의 상황입니다. 그런 경우에는 체인을 만들어 pi[7]을 구할 때처럼 p[i]와 p[j]가 같아질 때까지 공통인 구간의 길이를 줄여나갑니다. p[i]와 p[j]가 같아지는 구간이 없다면 pi[i] = 0이 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> get_pi(string p){
  int n = p.size();
  vector<int> pi(n);
  pi[0] = 0;
  int j = 0;
  for(int i=1; i<n; i++){
    while(j > 0 && p[i] != p[j]) j = pi[j-1];
    if(p[i] == p[j]){
      pi[i] = j+1;
      j++;
    }
  }
  return pi;
}

문자열 매칭하기

pi배열을 구했다면 이제 kmp로 string matching을 해봅시다.

kmp 알고리즘의 핵심적인 개념은 필요 없는 정보는 버린다. 입니다. 예시를 봅시다.
ABCDABCDABEE에서 ABCDABE를 찾아봅시다.

6번 인덱스에서 C-E가 다르기 때문에 매칭이 되지 않습니다.
만약 kmp를 사용하지 않고 Naive하게 탐색을 한다면 한 칸 뒤로 간 다음에 1번 인덱스부터 다시 탐색을 하겠죠. 그러나 pi배열을 구해놓았기 때문에 필요 없는 정보 는 버릴 수 있습니다. P의 6번 인덱스인 E에서 막혔습니다. 바로 전 인덱스인 5번 인덱스까지 봅시다.
pi[5] = 2입니다. 앞에 있는 AB와 뒤에 AB가 일치한다는 것이죠. P의 접두사 AB와 접미사 AB는 S의 특정 부분과 매칭이 되어 있으므로 아래 사진과 같이 이동해서 비교해도 됩니다.

앞에 두 글자 AB는 이미 같다는 것이 보장이 되어 있기 때문에 비교를 할 필요가 없습니다. C부터 비교를 하면 됩니다.

이런 방식으로 계산을 건너뛰면서 복잡도를 O(N + M)으로 줄일 수 있습니다.

kmp를 수행하는 코드 자체는 pi배열을 구하는 코드와 유사합니다.
아래 코드는 S에서 P를 모두 찾은 뒤, P의 시작점들을 반환하는 함수입니다.
참고로 i는 S에서 비교할 인덱스, j는 P에서 비교할 인덱스를 의미합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> kmp(string s, string p){
  vector<int> ans;
  int n = s.size(), m = p.size();
  vector<int> pi = get_pi(p);

  for(int i=0; i<n; i++){
    while(j > 0 && s[i] != p[i]) j = pi[j-1];
    if(s[i] == p[j]){
      if(j == m-1){
        ans.push_back(i-m+1);
        j = pi[j];
      }
      else j++;
    }
  }
}

while문은 pi를 구할 때 체인을 만들어 주는 것과 같습니다.
s[i] == p[j] 를 만족하는 경우, 다시 두 가지 케이스로 나눠집니다.

  1. j == m-1 인 경우에는 찾고자 하는 패턴 P의 마지막 글자까지 모두 매칭이 되었다는 것을 의미하므로 P를 온전히 찾은 것입니다. ans에 시작 위치를 넣어주면 됩니다.
  2. j != m-1 인 경우에는 완전히 찾은 것이 아니라 일정 부분까지만 일치한 것을 의미합니다. 그러므로 j를 1 증가시켜 다음 글자를 비교시킵니다.

여기까지가 kmp 알고리즘에 대한 설명입니다.