[알고리즘 정리] KMP(1/3)

문자열 패턴 매칭이란?

장문의 문자열(평문)에서 특정 패턴을 포함하고 있는지 혹은 포함하고 있다면 어느 위치에 포함하고 있는지 찾고자 하는 목표를 갖는 알고리즘입니다.

먼저 단순하게 문자열을 찾는다고 생각해보면, 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교할 수 있습니다.

다음과 같은 문자열 HELLOTHERE 이 주어지고, 그 안에서 LOTH 문자열을 찾으려고 한다면, 한 칸씩 이동해가면서 비교할 수 있을 겁니다.

이런 Brute-force 방식은 최악의 경우 주어진 문자열의 모든 한 글자를 시작으로 패턴 전체를 비교해봐야 하므로, O(NM) 의 시간 복잡도를 가집니다.

N : 문자열 길이, M : 패턴 길이

KMP 알고리즘

KMP 알고리즘은 위에서 본 Brute-force 방식의 문자열 매칭 알고리즘을 보다 효율적으로 개선시킨 알고리즘입니다.

불일치할 텍스트 문자열의 앞부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행합니다.

KMP 알고리즘은 O(N+M) 의 선형 시간 시간 복잡도를 가집니다.

N : 문자열 길이, M : 패턴 길이

문자열의 길이가 100,000이고 패턴 길이가 1000이라고 가정하면 아래와 같은 비교 횟수의 차이를 볼 수 있습니다.

• Brute-force 방식으로는 100,000 X 1000 = 1억 번
• KMP : 100,000 + 1000 = 101,000번

아래의 예를 보며 KMP의 핵심 아이디어에 대해 살펴봅니다. 먼저, 문자열의 인덱스 0에서 패턴의 부분 문자열 ABABA까지 일치하고 그 뒤는 다른 것을 볼 수 있습니다. 이 때, 문자열 뒤의 세 글자와 패턴 문자열 앞의 세 글자가 ABA로 일치합니다.

그렇다면, 다음 검사는 인덱스 1에서 이뤄지는 것이 아닌, 0에서 두 칸을 건너 뛰어 문자열의 인덱스 2부터 검사를 할 수 있게 됩니다. ABA라는 공통 문자열이 같음을 확인했기 때문입니다.

지나간 문자열의 뒤쪽과 검사하고자 하는 문자열의 앞쪽에서 서로 일치하는 문자가 몇 개인지를 알아내는 것이 KMP 알고리즘의 핵심입니다. 같은 문자열만큼만 겹쳐놓고, 다음 문자부터 새롭게 비교하는 과정을 거치면 되기 때문입니다.

이렇게 패턴 문자열의 부분 문자열로부터 자기 자신의 문자열을 제외하고, 길이가 되도록 길며, 접두사와 접미사가 같은 문자열이 몇 개인지를 저장한 배열을 pi 배열이라고 합니다. pi 배열의 각 요소는 몇 칸을 앞으로 이동해도 이전 문자열들이 일치하는 상태를 유지하는 가를 알려줍니다.

이제 검색하려는 패턴 문자열의 접두사와 접미사를 비교하여 pi 배열을 완성해보도록 하겠습니다.

패턴의 부분 문자열 A의 경우

• 자기 자신의 문자열이므로 해당 사항 없음.

⇒ pi[0] = 0

패턴의 부분 문자열 AB의 경우

• 길이 1
  • 접두사 : A
  • 접미사 : B

⇒ pi[1] = 0

패턴의 부분 문자열 ABA의 경우

• 길이 1
  • 접두사 : A
  • 접미사 : A
• 길이 2
  • 접두사 : AB
  • 접미사 : BA

⇒ pi[2] = 1

패턴의 부분 문자열 ABAB의 경우

• 길이 1
  • 접두사 : A
  • 접미사 : B
• 길이 2
  • 접두사 : AB
  • 접미사 : AB
• 길이 3
  • 접두사 : ABA
  • 접미사 : BAB

⇒ pi[3] = 2

패턴의 부분 문자열 ABABA의 경우

• 길이 1
  • 접두사 : A
  • 접미사 : A
• 길이 2
  • 접두사 : AB
  • 접미사 : BA
• 길이 3
  • 접두사 : ABA
  • 접미사 : ABA
• 길이 4
  • 접두사 : ABAB
  • 접미사 : BABA

⇒ pi[4] = 3

패턴의 부분 문자열 ABABAC의 경우

• 길이 1
  • 접두사 : A
  • 접미사 : C
• 길이 2
  • 접두사 : AB
  • 접미사 : AC
• 길이 3
  • 접두사 : ABA
  • 접미사 : BAC
• 길이 4
  • 접두사 : ABAB
  • 접미사 : ABAC
• 길이 5
  • 접두사 : ABABA
  • 접미사 : BABAC

⇒ pi[5] = 0

패턴의 부분 문자열 ABABACA의 경우

• 길이 1
  • 접두사 : A
  • 접미사 : A
• 길이 2
  • 접두사 : AB
  • 접미사 : CA
• 길이 3
  • 접두사 : ABA
  • 접미사 : ACA
• 길이 4
  • 접두사 : ABAB
  • 접미사 : BACA
• 길이 5
  • 접두사 : ABABA
  • 접미사 : ABACA
• 길이 6
  • 접두사 : ABABAC
  • 접미사 : BABACA

⇒ pi[6] = 1

위 과정을 통해 아래와 같은 pi 배열을 만들 수 있습니다.