KMP(Knuth Morris Pratt) 알고리즘 복습 노트

들어가기 앞서

이 포스트는 게시자가 KMP를 공부하면 뒤돌아서면 바로 까먹는 이유로 빠르게 복습하기 위해 만들었다.

 

처음부터 공부하고자 하는 이는 나동빈 유튜브에서 매우 직관적이고 잘 설명하고 있으므로 유튜브를 먼저 시청할 것을 강력 권고한다.

 

https://youtu.be/yWWbLrV4PZ8

KMP의 목적

찾고자 하는 문자열을 시간 복잡도와 공간 복잡도 각각 $O(|N| + |M|)$로 찾게 해 준다.

$O(|N| + |M|)$를 실현하는 원리

KMP는 접두사와 접미사가 일치할 때 그만큼 점프하여 속도를 개선하는 데 있다.

 

예를 들어 문자열 abahkaba 같은 경우 접두사와 접미사가 같은 부분은 abahkaba -> aba가 된다.

예시를 통한 알고리즘 이해

abacaaba를 가지고 접두사와 접미사 길이를 찾아본다.

 

i, j 위치	j	i
문자열	a	b	a	c	a	a	b	a
접미사 = 접두사	0

둘이 일치하지 않음. i만 증가

 

i, j 위치	j		i
문자열	a	b	a	c	a	a	b	a
접미사 = 접두사	0	0

둘이 같음. 공통 길이 1 되고 i, j 증가

 

i, j 위치	j	<- j		i
문자열	a	b	a	c	a	a	b	a
접미사 = 접두사	0	0	1

둘이 같지 않음. j는 0으로 돌아가고 i만 증가

 

i, j 위치	j				i
문자열	a	b	a	c	a	a	b	a
접미사 = 접두사	0	0	1	0

둘이 같음. j와 i 증가하고 공통 길이 1

 

i, j 위치	j	<- j				i
문자열	a	b	a	c	a	a	b	a
접미사 = 접두사	0	0	1	0	1

둘이 같지 않음. j는 0으로 돌아가고 다시 비교. 둘이 같으므로 1 채우고 j, i 증가

 

i, j 위치		j					i
문자열	a	b	a	c	a	a	b	a
접미사 = 접두사	0	0	1	0	1	1	2

둘이 같음. 2를 채우고 j, i 증가

 

i, j 위치			j					i
문자열	a	b	a	c	a	a	b	a
접미사 = 접두사	0	0	1	0	1	1	2	3

둘이 같음. 3을 채운다.

실패 함수 코드

vector<int> bake_pi(string &pat) {
  int sz = pat.size();
  vector<int> ret(sz);

  int j = 0;
  for (int i = 1; i < sz; i++) {
    while (j and pat[i] != pat[j]) j = ret[j - 1];
    if (pat[j] == pat[i]) ret[i] = ++j;
  }

  return ret;
}

실패 함수로 문자열 찾기

위에서 구축한 테이블로 ababacabacaabacaaba에서 abacaaba를 찾는 매칭을 해본다.

 

ababacabacaabacaaba

a

 

ababacabacaabacaaba

ab

 

ababacabacaabacaaba

aba

 

ababacabacaabacaaba

abac

여기서 맞지 않는다. 이때 공통 접/미두사는 a이고 우리는 이 접두사가 일치하는 부분부터 다시 탐색을 시작한다.

 

ababacabacaabacaaba

ab

그러면 이렇게 ab부터 검사하게 된다.

 

ababacabacaabacaaba

aba

 

ababacabacaabacaaba

abac

 

ababacabacaabacaaba

abaca

 

...

 

ababacabacaabacaaba

abacaaba

 

이렇게 해서 일치하는 패턴을 찾는다. 물론 이 이후에도 검색을 계속하여 일치하는 모든 부분을 찾게 된다.

KMP 구현

vector<int> bake_pi(string &pat);

vector<int> kmp(string &target, string &pat) {
  vector<int> ret;
  auto pi = bake_pi(pat);

  int j = 0;
  for (int i = 0; i < target.size(); i++) {
    while (j and target[i] != pat[j]) j = pi[j - 1];
    if (target[i] != pat[j]) continue;
    if (j == pat.size() - 1) {
      ret.push_back(i - j);
      j = pi[j];
    } else {
      ++j;
    }
  }
  return ret;
}