[Algorithm] KMP

문자열 검색 알고리즘

텍스트 ABCABCABCDE 에서 ABCABC 와 일치하는 문자열을 찾아보자

가장 일반적인 방법은 찾을 패턴을 한 자리씩 옮기면서 찾아가는 방법이다.

A	B	C	A	B	C	A	B	C	D	E
A	B	C	A	B	C	A

A	B	C	A	B	C	A	B	C	D	E
	A	B	C	A	B	C	A

A	B	C	A	B	C	A	B	C	D	E
		A	B	C	A	B	C	A

A	B	C	A	B	C	A	B	C	D	E
			A	B	C	A	B	C	A

…

기존 텍스트의 길이 N, 패턴의 길이를 M 이라 할때 모든 자리에 대해서 하나하나 모두 하면 O(NM) 이다.

이때 KMP 알고리즘을 사용하게 되면 O(N+M)으로 문자열을 검색할 수 있다.

KMP 알고리즘

KMP 알고리즘은 위와 같은 경우에서 첫 번째 문자열 비교 후 두 번째와 세 번째는 검사하지 않고 바로 네 번째로 이동할 수 있는 알고리즘이다. 이를 위해서는 먼저 접두어와 접미어가 같을 수 있는 가장 긴 길이를 구해야한다!

예를 들어 위와 같은 경우로 ABCABCA 가 존재할 때 i 번째 문자열까지의 부분 문자열과 그때 접두어와 접미어가 가장 긴 길이를 length 라 하자.

i	문자열	length[i]
0	A	0
1	AB	0
2	ABC	0
3	ABCA	1
4	ABCAB	2
5	ABCABC	3
6	ABCABCA	1

위와 같이 나타낼 수 있다.

A	B	C	A	B	C	A	B	C	D	E
A	B	C	A	B	C	A

A	B	C	A	B	C	A	B	C	D	E
			A	B	C	A	B	C	A

그럼 다시 위와같을 때 왜 한번에 3칸 다음으로 이동할 수 있을지 생각해보자. 이미 일치하는 문자의 개수는 5이며 length[5] = 3 이다. 이를 생각해보면 이미 일치하는 칸을 확인했다면 접미어 부분을 다음 확인시에는 접미사 부분으로 바로 이동시킬 수 있다는 것이다.

구현

void kmp(char[] str, char[] pattern) {
  int[] table = KMP_Table(pattern);

  int j = 0;
  for (int i = 0; i < str.length; i++) {
    while (j > 0 && str[i] != str[j]) {
      j = table[j - 1];
    }

    if (str[i] == pattern[j]) {
      if (j == pattern.length - 1) {
        //i - parttern.length + 1 에서 발견!
        j = table[j];
      } else {
        j++;
      }
    }
  }
}

j = table[j-1] 를 한 번만 하는 것이 아니라 str[i] != str[j] 이면 while 문을 돌려서 최대한으로 계속해서 점프한다! 첫번째 for 문에서 주어진 str 을 처음부터 계속해서 맞춰나가다가 불일치하는 부분이 생기면 이전까지 일치하는 부분의 접미어 접두어 최대 길이를 구해 다시 일치하는 부분까지 땡겨주는 것이다.

int[] KMP_Table(char[] pattern) {
  int[] table = new int[pattern.length];
  int j = 0;
  for (int i = 1; i < pattern.length; i++) {
    while (j > 0 && pattern[i] != pattern[j]) {
     j = table[j - 1];
   }
  if (pattern[i] == pattern[j]) {
    table[i] = ++j;
    }
  }
  return table;
}

패턴의 테이블을 구할 때도 KMP 가 그대로 사용되는 것을 볼 수 있다. 기존 kmp 에서 str이 한 칸씩 늘어나면서 기존 위치의 pattern 도 한칸씩 늘어나면서 검사한다. 일치하면 pattern[j] = pattern[j-1]+1, 불일치하면 j = pattern[j-1] 을 while 문으로 다시 검사할 수 있다!

참조 : https://bowbowbow.tistory.com/6