문자열 - KMP

나는 문자열 알고리즘을 개인적으로 별로 좋아하지 않는데, 특히 kmp는 유난히 이해가 잘 되지 않아서 계속 글 쓰기를 미뤄놓고 있었다. 하지만 class 6에 kmp 문제가 등장하기도 하고 슬슬 한번쯤 다뤄야 할 주제인 것 같아 정리해 본다.

 

KMP(Knuth-Morris-Pratt) 알고리즘은 단일 문자열 서칭에 있어 가장 강력한 알고리즘 중 하나이다. 문자열 $T$ 내에서, 찾아야 하는 대상인 패턴 문자열 $P$가 어디에 등장하는지 구하는 문제가 주어졌다고 가정해 보자. $T$의 모든 인덱스를 시작점으로 하여 패턴과의 일치 여부를 비교하는 경우 최악에는 두 문자열 길이의 곱인 $O(NM)$만에 동작할 것이다. 물론 $P$가 길지 않은 경우에는 큰 문제가 없으며 패턴과 일치하지 않는 순간 바로 break하는 알고리즘을 생각해 볼 수 있으나, $T=aaa...aaa, P=aaa...aab$와 같이 끝 부분이 불일치하는 경우 큰 시간 손해를 보게 된다. kmp는 이러한 중복을 제거하여 서칭에 걸리는 시간을 $O(N+M)$으로 단축시켜 준다.

 

 

실패 함수와 KMP의 동작 원리

kmp의 핵심은 실패 함수로, 실패 함수의 작동을 잘 이해해야 한다. 실패 함수는 다음과 같이 정의된다.

 

$fail[i]$ = ($P$의 부분 문자열 $(P[0] \cdots P[i])$에서, prefix와 suffix가 일치하는 최대 길이)

= ($(P[0] \cdots P[k-1]) = (P[i-k+1] \cdots P[i])$ and $P[k] \neq P[i-k]$인 $k$)

 

즉 $k$ 직전까지는 부분 문자열의 prefix와 suffix가 일치하다가, $k$일때 그렇지 못한 경우 $k$를 실패 함수 값으로 정의하는 것이다. 실패 함수를 활용하면, $T[i-1]$과 $P[j-1]$까지의 매칭이 성공하고 $T[i]$와 $P[j]$의 매칭이 실패하였을 때, 다시 $P[0]$부터 검사할 필요가 없다. $fail[j-1]=k$라 하면, 이미 $(T[i-k] \cdots T[i-1])$과 $(P[0] \cdots P[k-1])$의 일치는 보장되어 있기 때문이다. 따라서 $T[i]$와 $P[k]$의 매칭을 시도하면 된다. 이 논리는 간단하게 다음의 표현으로 나타낼 수 있다.

 

$$j := fail[j-1]$$

 

이것이 kmp 알고리즘의 핵심이다. 실패 함수를 미리 구해 놓고, $T[i]$와 $P[j]$의 매칭이 성공할 때까지 위 알고리즘을 반복하다가 성공하면 $i, j$를 함께 1씩 증가시키면 된다.

res = []
j = 0
for i in range(len(T)):
    while j > 0 and T[i] != P[j]: j = fail[j-1]
    if T[i] == P[j]:
        if j == len(P)-1:
            res.append(i-j+1)
            j = fail[j]
        else:
            j += 1

 

시간복잡도 분석을 해 보자. $j$는 매칭에 성공하면 1씩 증가하는데 1씩 내려가는 최악의 경우에도 증가했던 만큼만 감소할 수 있다. 따라서 $O(N)$의 선형 시간에 문제 해결이 가능하다.

 

 

실패 함수의 구현

전처리에 해당하는 실패 함수의 구현은, 놀랍게도 kmp의 아이디어를 재귀적으로 사용한다. 이번엔 $T$에서 $P$의 부분 문자열 일치를 확인하는 것이 아니라, $P$ 내에서 $P$의 부분 문자열이 얼마나 일치하고 있는지 확인하면 되기 때문이다. 정의상 $fail[0]=0$이므로 $i$가 1부터 시작한다는 점만 제외하면, 코드가 거의 일치하는 것을 볼 수 있다. 실패 함수의 구현은 기존 값을 활용한다는 점에서 일종의 dp라고도 볼 수 있을 것 같다. 어쨌든 이 역시 $O(M)$ 안에 처리할 수 있음이 자명하다.

fail = [0]*len(P)
j = 0
for i in range(1, len(P)):
    while j > 0 and P[i] != P[j]: j = fail[j-1]
    if P[i] == P[j]: 
        j += 1
        fail[i] = j