KMP법

KMP법이란?

브루트-포스법에서는 다른 문자를 만나면 패턴에서 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 재검사를 했습니다. 하지만, 이것은 비효율적입니다. 그래서 KMP법은 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘입니다. (참고로 이 알고리즘은 만든 사람이 Knuth, Morris, Prett이기 때문에 앞글자를 하나씩 따서 KMP알고리즘이라고 불립니다.)

구현 방식

KMP 알고리즘을 이해하기 위해 먼저 알아야 할 것이 2가지 있습니다.

1. 접두사(prefix)와 접미사(suffix)입니다.
2. skip배열

하나씩 확인해보겠습니다.

Prefix, Suffix

예시로서 먼저, “banana”의 접미사, 접두사를 보면 무엇인지 이해할 수 있습니다.

• banana의 접두사: [b, ba, ban, bana, banan, banana]
• banana의 접미사: [a, na, ana, nana, anana, banana]

이렇게 각각 6개씩 존재합니다.

Skip 배열(pi[])

사실 이 부분이 제일 이해하기 힘들 수 있는데, 먼저 구분을 잘 해놔야 합니다.

Skip배열의 필요성은 Text와 Pattern의 비교 과정에서 불일치 하는 문자가 발생 했을 때 비교 과정에서 확인한 문자열을 가지고 패턴을 움직이기 위해서 사용하는 배열이라고 생각하면 됩니다.

다음 예시를 확인해 보겠습니다.

0	1	2	3	4	5	6	7	8	9	…
A	B	C	A	B	X	?	?	?	?	?
A	B	C	A	B	D

위의 과정은 5번째 Index에서 불일치 문자가 나오고 0번 ~ 4번 Index까지 비교하는 과정에서는 문자가 일치하는 경우입니다. 근데 패턴에서 일치하는 문자열을 보면 0 ~ 1번 문자열 “AB”와 3 ~ 4번 문자역 “AB”가 일치합니다. 그래서 패턴을 오른쪽으로 3칸 이동시키면 “AB”는 일치한 상태로 놓여지게 될 것입니다. 해당 상황은 다음과 같습니다.

0	1	2	3	4	5	6	7	8	9	…
A	B	C	A	B	X	?	?	?	?	?
			A	B	C	A	B	D

여기서 “AB”는 일치하도록 옮겼기 때문에 5번 위치부터 다시 비교를 시작하면 되겠습니다.

이와 같이 이용할 수 있도록 Skip배열은 전처리 과정을 거쳐서 미리 구해놓습니다.

이제 표를 작성해 볼 것인데, 미리 알아둬야 할 것이 있습니다.

• 포인터 개념 사용
• Skip Table의 Index = 포인터의 위치
• Skip Table의 Value = 해당 포인터에 놓여야할 문자의 위치(Index) (! 이동시켜야 되는 정도 X !)

예를 들어서, 위의 상황 같은 경우는 일치하는 문자열의 크기가 5이고, 현재 포인터의 위치는 5번 Index에 위치하고 있습니다. 따라서, Skip[5] = 2이면 되는 것입니다. 그렇게 포인터의 위치는 그대로 냅두고 비교를 다시 시작하면, 이미 3번 4번 위치는 일치한 상태로 비교를 하는 것(패턴의 2번째 Index부터 비교)입니다.

저는 패턴 문자열을 박스라고 생각하고 포인터는 가만히 둔 채 박스만 이동시킨다고 생각하면 이해하기 편했습니다.

표를 작성할 때는 패턴 안에서 중복되는 문자열을 먼저 찾아야 합니다. 이 과정에서 KMP법을 사용합니다. 패턴 안에서 중복되는 문자의 나열을 찾기 위해 패턴을 겹쳐놓고 생각해보겠습니다.

예시로서, 패턴 “ABCABD”를 겹쳐 가면서 확인해 보겠습니다.

1. Skip[1] -> Index 1번 위치에서 불일치 문자가 나온 경우

해당 경우는 한개의 문자 일치로 어차피 비교할 수 있는 접두사와 접미사가 없기 때문에 본문의 포인터(Index 1 위치에 해당)는 냅둔 채 패턴의 0번째 Index와 다시 비교해야하기 때문에 무조건 Skip[1] = 0이다. (즉, 1칸 이동)

2. Skip[2] -> Index 2에서 불일치 문자가 나온 경우

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

“AB”에서 접두사 “A”와 접미사 “B”가 불일치 하므로 Skip[2] = 0입니다. 패턴, 포인터를 1칸 이동합니다.

3. Skip[3]

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

4. Skip[4]

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

“ABCA”에서 접두사 “A”와 접미사 “A”가 일치하므로 Skip[4] = 1 입니다. 포인터만 1칸 이동합니다.

5. Skip[5]

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

“ABCAB”에서 접미사 “AB”와 접두사 “AB”가 일치하므로 Skip[5] = 2입니다. 포인터만 1칸 이동합니다.

6. Skip[6]

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

현재 본문과 패턴의 비교를 생각해 봤을 때 “ABCABD”까지 비교(확인)가 전부 된 상황일 것이다. 전부 일치할 경우 얼만큼 패턴을 이동시켜야 할까를 구하는 것이다. 확인해 봅시다.

현재 Skip[5]에서는 2개가 일치하여 포인터만 옮겼는데 “D”와 “C”가 일치하지 않습니다. 그래서 패턴을 2칸 이동시키고 다시 비교를 해봐도 일치하지 않기 때문에 Skip[6] = 0으로 됩니다.

이렇게 표 만들기가 끝났습니다.

이 부분은 본인도 굉장히 헷갈렸던 부분이였습니다. 코드를 보면서 위에서 강조한 것을 확인해가며 이해하면 충분히 이해할 수 있습니다.

코드

int kmpMatch(String txt, String pat) {
  int pt = 1;   // txt 커서
  int pp = 0;   // pat 커서
  int[] pi = new int[pat.length() + 1];   // 건너뛰기 표

  // 건너뛰기 표(pi)를 만듭니다.
  // 표를 만들떄는 일치하는 숫자 갯수 라는 개념이 강하게 생각됨 
  pi[pt] = 0;
  while (pt != pat.length()) {
    if (pat.charAt(pt) == pat.charAt(pp))
      pi[++pt] = ++pp;
    else if (pp == 0)
      pi[++pt] = pp;
    else
      pp = pi[pp];
  }

  // 검색
  // 검색 과정에선 포인터의 개념이 강하게 생각됨
  pt = pp = 0;
  while (pt != txt.length() && pp != pat.length()) {
    if (txt.charAt(pt) == pat.charAt(pp)) {
      pt++;
      pp++;
    } else if (pp == 0)
      pt++;
    else
      pp = pi[pp];
  }

  if(pp == pat.length())
    return pt - p p;
  
  // fail Search
  return -1;
}

시간 복잡도

KMP 알고리즘의 최악의 상황을 생각해 봅시다.

문자열 매칭이 항상 탐색 문자열의 마지막 문자 직전까지는 성공하고, 마지막 문자에 실패하는 경우가 최악의 상황일 것이다.

이때 시간 복잡도는 어떻게 될까?

1. 우선 포인터(pt, pp)가 탐색 문자열(패턴)의 길이 - 1만큼 증가할 것입니다.
2. 그 이후 문자열 불일치가 탐색 문자열의 마지막 문자에 발생했으므로, pp = pi[pp]로 접두 접미사의 길이만큼 계속 감소하게 될 것입니다.

이때 접두 접미사의 길이는 항상 현재 탐색 문자열의 길이보다 1이상 작으므로 최대 pp회 만큼 감소하면 0이 됩니다.

예를 들어, 탐색 문자열(패턴)이 “AAAAA” 일때, 접미사는 “AAAA” 입니다. 접두 접미사가 탐색 문자열 자신보다 항상 짧은 걸 알 수 있습니다.

최악의 상황에서 1번, 2번 상황이 반복되었을 경우, pp가 패턴의 마지막 요소까지 갔다가 하나씩 줄어들어 결국 패턴의 첫번째 요소로 떨어지는 경우일 것입니다. 텍스트의 문자열의 길이를 N, 패턴의 문자열 길이를 M이라고 했을 경우, 1번에서 pt와 pp가 M회 만큼 소요해서 이동했다가, pp가 M회만큼 소요해서 다시 맨 처음 인덱스로 돌아가는 과정이 반복될 것이다. 즉, M만큼 이동하는데 $2*M$만큼 시간을 소모한 것입니다. 그렇다면, 이렇게 생각을 해볼 수 있습니다. 문자열을 탐색할 때 오른쪽으로 방향으로 진행하는 것(pt)은 결국 N개의 문자를 탐색을 할 것이고, 돌아오는 과정(pp)이 k번 일어 났다면 N + kM이라고 쓸 수 있습니다.
그래서 시간 복잡도는 $O(N + M)$으로 처리 됩니다.

놀랍게도, 이 이하로 더 빠른 알고리즘을 고안하기 매우 어렵다는 것입니다.

간단하게 생각해봐도, 원본 문자열과 탐색할 문자열을 단 1번씩 만 읽어도 O(N + M)의 시간 복잡도가 소요됩니다.

따라서, O(N + M)이하의 시간복잡도라면 원본 문자열과 탐색할 문자열 중 일부를 읽지 않아도 탐색이 가능하다는 소리입니다. 이는 불가능에 가깝다는 것을 이해할 수 있습니다.

---

Reference

• Do it! 자료구조와 함께 배우는 알고리즘 입문(자바 편)(이지스 퍼블리싱)
• KMP : 문자열 검색 알고리즘 - 멍멍멍