PS 문자열 알고리즘 - 1. KMP 알고리즘

 

문자열 알고리즘 블로그의 첫 시작은 KMP로 정했다. KMP 알고리즘은 해결하고자 하는 문제 상황 자체가 매우 단순하고 기초적이기 때문에 첫 시작으로 적합하다는 생각이 들었다. 이번 글에서는 KMP 알고리즘의 원리에 대해 다루고자 하며, 다음 글에서는 KMP 알고리즘을 활용하는 문제들을 다양하게 다뤄보고자 한다.

 

KMP 알고리즘(Knuth - Morris - Pratt Algorithm)은 특정 패턴이 문자열의 어디에서 나타나는지 빠르게 찾기 위한 문자열 검색 알고리즘이다. 자세한 내용은 아래 문제에서 확인하자.

 

먼저 아래 문제를 살펴보자. https://www.acmicpc.net/problem/1786

 

문제 상황은 문자열 내에서 다른 문자열이 어디에 속해 있는지 모두 찾는 것이다. 우리가 자주 사용하는 Ctrl + F 같은 탐색을 생각하면 이해가 용이할 것하다.

 

 

문제 지문 자체에 KMP 알고리즘의 핵심 아이디어가 잘 적혀 있다. 이를 여기서 다시 한 번 간략히 정리해보자.

      1 2 3 4 5 6 7 8 9 …
T : [ A B A D A B A D A B D E ]
      | | | | | | X
P : [ A B A D A B D ]
      1 2 3 4 5 6 7

 

 

<BOJ 1786 찾기> 문제 본문의 문자열을 설명의 편의를 위해 살짝 바꾸어 가지고 왔다. 문자열 T에서 문자열 P가 어디에 있는지 찾는 상황이다. 위는 T와 P를 1번째 문자부터 순서대로 매칭을 했더니 T와 P의 7번째 문자가 서로 달라 탐색에 실패한 상황이다.

 

일반적인 브루트포스 알고리즘을 사용한다면 여기서 P의 위치를 아래와 같이 옮기는 것을 생각할 수 있다.

      1 2 3 4 5 6 7 8 9 …
T : [ A B A D A B A D A B D E ]
        X
P :   [ A B A D A B D ]
        1 2 3 4 5 6 7

 

 

이 예제에서는 P를 1칸 이동하여 매칭을 하려는 순간 첫 글자부터 문자가 일치하지 않기 때문에 탐색 시간이 아주 느리지는 않을 것이다. 하지만 이렇게 P를 1칸씩 밀어가면서 탐색할 시 시간복잡도는 $O(NM)$이 된다. ($N$은 문자열 T의 길이, $M$은 문자열 S의 길이)

 

우리는 이미 1번째 탐색을 하면서 T의 1~6번째 문자와 P의 1~6번째 문자, 이렇게 6개의 문자가 매칭된다는 사실을 알게 되었다. 이 정보를 이용해서 굳이 탐색하지 않아도 될 P의 위치는 건너뛰고, 필요한 곳만 탐색할 수 없을까? 라는 아이디어에서 출발한 것이 KMP 알고리즘이다. 이 예제에서는 아래와 같이 불필요한 위치를 건너뛰고, 탐색이 필요한 위치인 P를 4번 이동해 T의 5번째 문자와 P의 1번째 문자가 대응되는 상황으로 빠르게 이동해야 할 것이다.

      1 2 3 4 5 6 7 8 9 …
T : [ A B A D A B A D A B D E ]
              | | | | | | |
P :         [ A B A D A B D ]
              1 2 3 4 5 6 7

 

 

7번째 탐색에서 실패했으므로 P와 T의 1~6번째 문자는 동일하다는 사실을 이미 알고 있다. 즉, 우리가 지금 알고 있는 정보는 아래와 같다.

      1 2 3 4 5 6 7 8 9 …
T : [ A B A D A B A ? ? ? ? ? ]
      | | | | | | X
P : [ A B A D A B D ]
      1 2 3 4 5 6 7

 

 

 

그렇다면 P의 1번째 문자를 T의 2번째 문자와 매칭하려는 시도는 의미가 있을까? 그렇지 않다. T의 2번째 문자는 P의 2번째 문자와 같은데, P의 2번째 문자는 1번째 문자와 다름을 알기 때문이다.

 

P의 1번째 문자를 T의 3번째 문자와 매칭하려는 시도는 어떨까? 언뜻 보기에는 T의 3번째 문자는 P의 3번째 문자와 같고, 이는 다시 P의 1번째 문자와 같으니까 의미가 있어 보일 수 있다. 하지만 우리는 이보다 많은 정보를 알고 있다. T의 4번째 문자는 P의 4번째 문자와 같고, 이는 P의 2번째 문자와 다르기 때문에 불필요한 탐색이 될 것이다.

 

한편, P의 5번째 문자를 T의 1번째 문자와 매칭하려는 시도는 어떤가? T의 5-6번째 문자가 P의 5,6번째 문자와 같고, 이는 P의 1,2번째 문자와 같으므로 필요한 탐색이 된다.

 

불필요한 탐색과 필요한 탐색의 차이를 도식화하면 아래와 같다.

 

불필요한 탐색의 예시
       1 2 3 4 5 6 7 8 9 …
T  : [ A B A D A B A D A B D E ]
       | | | | | | X
P1 : [ A B A D A B D ]
           | | | |  (불일치)
P2 :     [ A B A D A B D ]

필요한 탐색의 예시
       1 2 3 4 5 6 7 8 9 …
T  : [ A B A D A B A D A B D E ]
       | | | | | | X
P1 : [ A B A D A B D ]
               | |  (일치)
P2 :         [ A B A D A B D ]

 

 

그림을 통해 차이점을 아마 쉽게 알 수 있을 것이다. 필요한 탐색이 되려면 P2의 접두사 부분은 P1에서 탐색이 실패하기 직전의 접미사 부분과 공통된 문자열을 가져야 한다! 그리고 필요한 탐색 중 가장 먼저 등장하는 것으로 이동해야 성공한 매칭을 놓치지 않으므로 공통된 문자열의 길이는 최대화되어야 한다. 따라서 이를 종합할 때 P1과 P2는 결국 같은 문자열이기 때문에 P를 적당히 잘랐을 때 접미사와 접두사에서 공통이면서 길이가 최장인 문자열의 길이를 알면 다음 필요한 탐색이 어디인지 알 수 있다.

 

그리고 이런 방식의 효용은 문자열 T와 무관한 패턴이므로 P가 주어졌을 때 미리 전처리할 수 있다는 점에 있다.

 

일치해야 하는 부분은 P2에서는 항상 앞부분이고, P1은 탐색이 실패한 부분부터이므로 P에 관한 전처리 배열을 만들고, $i$번 인덱스에는 P를 맨 앞부터 $i$번째 인덱스까지 잘랐을 때 접두사임과 동시에 접미사인 최대 문자열의 길이를 저장할 것이다. (그러한 공통 접두사/접미사가 존재하지 않는다면 0을 저장하며, 전체 문자열은 접두사나 접미사로 간주하지 않는다.) 그리고 이 값들을 문자열 매칭에 실패했을 때 이동할 위치를 찾을 때 사용하는 함수라서 실패 함수 (failure function)이라고 부른다.

 

즉, P가 위의 예시처럼 ABADABD로 주어진 경우, 전처리 배열 F에는 $[0, 0, 1, 0, 1, 2, 0]$이 저장된다. 예시를 들면 아래와 같다. (여기서부터는 후에 작성할 코드와 호환을 위해 0-base index를 사용할 것이다.)

i = 2인 경우

[A] B [A] 

F[2] = 1

i = 5인 경우

[A B] A D [A B]

F[5] = 2

 

그런데, 우리가 이 실패 함수 역시 빠른 속도로 구해야 전체 시간복잡도가 줄어들 것이다.

이는 실패함수를 순차적으로 구하면서 전에 구한 값을 이용함으로써 해결한다.

 

편의상 새로운 예시 문자열 A B A B B C A B A B A를 들어 설명하겠다.

 

A B A B B C A B A B A 에서 $i = 8$까지의 실패함수 배열 $[0, 0, 1, 2, 0, 0, 1, 2, 3]$을 구한 상황을 가정하자.

 

$i = 9$일 때의 실패함수 값은 아래와 같이 구해진다. $j$는 새롭게 추가된 문자와 비교할 문자의 위치를 가리키는 포인터로 생각하면 된다.

i = 8)
[A  B  A] B  B  C [A  B  A]
          |
          j

i = 9)
[A  B  A] B  B  C [A  B  A] B
          |
          j

[A  B  A  B] B  C [A  B  A  B]
             |
             j

 

포인터 $j$에 놓인 문자와 새롭게 추가된 문자가 B로 일치한다. 따라서 공통 접두&접미사에 그대로 추가된 문자를 포함하고 $F[9] = F[8] + 1 = 4$가 된다. 한편 $i = 10$일 때는 어떤가?

i = 9)
[A  B  A  B] B  C [A  B  A  B]
             |
             j

i = 10)
[A  B  A  B] B  C [A  B  A  B] A
             |
             j

 

F[9]의 공통 접두&접미사인 A B A B에서 다음에 와야 할 문자는 B인데 추가된 문자는 A이므로 매칭되지 않는다. 이때에는 실패함수의 값을 어떻게 구할까?

 

이때는 실패 함수의 값이 줄어든다. 이는 $j$ 인덱스의 위치가 줄어들면서 확인하게 되는데, 이때 역시 접두사와 접미사가 공통으로 되는 문자열을 찾는 것이므로 아래 그림과 같이 위치를 옮기는 상황을 고려할 수 있다.

 

..C [A  B  A  B] A  ...
          [A  B  A  B] B ...

 

이는 놀랍게도 이미 $F[j-1] = F[3]$에서 우리가 구한 정보를 이용할 수 있기 때문에 A B가 이미 매칭된다는 것을 바로 확인할 수 있고, 새로 추가된 문자와 포인터 j가 가리키는 값이 같으므로 포인터 j의 위치를 오른쪽으로 1 옮기고 실패 함수 값을 결정할 수 있다. 이를 도식화하면 아래와 같다.

i = 9)
[A  B  A  B] B  C [A  B  A  B]
             |
             j

i = 10)
[A  B  A  B] B  C [A  B  A  B] A
             |
             j

[A  B] A  B  B  C  A  B [A  B] A
       |
       j
       
[A  B  A] B  B  C  A  B [A  B  A]
          |
          j

 

매칭이 안 되는 경우가 반복된다면 j가 0까지 이동하게 되고, 이때에도 매칭되지 않으면 실패 함수의 값은 0으로 남게 된다.

 

그러면 실패 함수 값을 우리가 구해냈으니, 다시 원래의 문제로 돌아와보자.

탐색에 실패한 경우 필요한 탐색으로 이동하는 것을 미리 구해놓은 실패함수의 값을 이용해서 쉽게 찾을 수 있다. 이때 탐색에 실패한 이후 필요한 탐색으로 바로 넘어가기 위해서 어떤 행동을 해야 하는지 생각해보자. 이를 위해 위에서 제시한 필요한 탐색 예시를 다시 가져오자.

                   i
                   |
       0 1 2 3 4 5 6 7 8 9 …
T  : [ A B A D A B A D A B D E ]
       | | | | | | X
P1 : [ A B A D A B D ]
       0 1 2 3 4 5 6
               | |
P2 :         [ A B A D A B D ]
               0 1 2 3 4 5 6
                   |
                   j

 

P1에서 탐색을 실패하였으므로 P2로 P 문자열을 옮기는 과정인데, 실제로는 문자열을 옮기는 것이 아니라 j 포인터의 위치를 옮기는 것이므로 i 포인터의 위치는 옮기지 않아도 충분하고, j 포인터의 경우 기존 6에 있었는데, 앞쪽에서 이미 매칭된 부분 A B A D A B의 실패 함수를 찾아야 하므로 j-1의 실패함수 위치로 이동하게 됨을 알 수 있다. (j-1의 실패함수가 A B가 공통 접두&접미사가 되어 2이다.)

 

 

이러한 원리를 합쳐서 종합적으로 구현한 KMP 알고리즘은 아래와 같다. 아래 코드는 <BOJ 1786 찾기> 문제의 정답 코드이기도 하다.

 

s1 = input().rstrip()
s2 = input().rstrip()

# 실패 함수 구하는 과정
failf = [0] * len(s2) # failure function
j = 0
for i in range(1, len(s2)):
    while j > 0 and s2[i] != s2[j]:
        # 탐색 실패 시 j 포인터 이동
        j = failf[j-1]
    if s2[i] == s2[j]:
        # 매칭 성공 시 실패 함수값 저장
        j += 1
        failf[i] = j

# 실패 함수를 이용해 문자열 매칭하는 과정
result = []
j = 0
for i in range(len(s1)):
    while j > 0 and s1[i] != s2[j]:
        # 탐색 실패 시 필요한 탐색 위치로 이동
        j = failf[j-1]
    if s1[i] == s2[j]:
        j += 1
        if j == len(s2):
            # s2 문자열 끝까지 매칭한 경우 위치 저장
            result.append(i-j+2)
            j = failf[j-1]
print(len(result))
print(*result, sep='\n')

 

그리고 중요한 것은 시간복잡도 분석이다. 기존의 Naive 방식의 시간복잡도가 $O(MN)$이었는데, KMP 알고리즘은 얼마나 개선되었을까?

 

얼핏 보기에는 while문이 많아 정확한 시간복잡도를 예측하기 어려워 보이기도 하지만, 아래와 같이 $O(M+N)$임을 증명할 수 있다.

[1] 실패 함수 계산 과정의 시간복잡도는 $O(M)$이다.

$i$는 1부터 (s2의 길이)-1, 즉 $M-1$까지 증가하므로 $O(M)$번 변한다.

이때 실패 함수의 값은 $j$로 정해지는데 $j$가 증가할 때 반드시 1씩 증가하므로 증가 횟수는 $O(M)$번이다. 또한 $j > 0$ 조건이 걸려 있는 상태로 $j$가 $j = F[j-1]$로 감소하므로 감소 횟수는 증가 횟수를 넘어설 수 없다. 따라서 감소 횟수도 $O(M)$번 안쪽으로 들어오기 때문에 $j$의 변화도 $O(M)$이 되어 실패 함수를 구하는 과정의 시간복잡도가 $O(M)$이다.

 

[2] 검색 단계의 시간복잡도는 $O(N+M)$이다.

이때 역시 [1]과 같은 이유로 $O(N)$이 되는데, $i$는 1부터 (s1의 길이)-1까지 증가하므로 $O(N)$번 변한다.

$j$는 s2를 가리키는 포인터이므로 최댓값이 $M$이고 증가 횟수가 $O(M)$번이다. 역시 $j > 0$ 조건이 걸려 있는 상태로 $j$가 감소하므로 감소하는 횟수도 $O(M)$번이 되어 검색 단계의 전체 시간복잡도가 $O(M+N)$이다.

 

[1], [2]를 종합하면 KMP 알고리즘의 시간복잡도가 $O(M+N)$이 됨을 알 수 있다.

 

이렇게 이번 글에서는 KMP 알고리즘의 원리에 대해 알아보았다. 다음에는 KMP 알고리즘을 활용하는 문제들에 대해 다뤄보겠다.

 

+ 이해가 안 되는 부분이 있거나 설명에 잘못된 내용이 있다면 댓글로 알려주시면 감사하겠습니다.