문자열 탐색에서 사용되는 KMP 알고리즘에 대해서

*글의 내용은 KMP : 문자열 검색 알고리즘을 참조했으며 글의 내용 및 구현 코드 모두 작성자 멍멍멍님께서 작성하신 예시, 코드를 그대로 사용했습니다.

작성된 내용을 이해하고, 내 것으로 만드는 과정을 위해 글을 작성했음을 말씀드립니다.

문자열 탐색, O(N*M)의 시간복잡도

어떤 문자열(S)에서 패턴(P)가 몇 번 등장하는지 찾고자 한다고 가정해봅시다.

가장 간단한 방법은 문자열 S의 인덱스 0부터 시작하여 P가 일치하는지 여부를 확인하는 것입니다. 이를 표로 표현해보면 아래와 같을 것입니다.

S의 인덱스 0부터 확인을 시작하여, 1, 2, 3을 차례로 비교하다가 보면,

아래처럼 S의 인덱스가 13인 지점에서 패턴 P가 등장함을 확인할 수 있습니다.

문제는 위와 같은 알고리즘의 시간복잡도가 매우 높다는 점입니다.

문자열 S의 길이를 N, P의 길이를 M이라고 했을 때 모든 S 인덱스에 대해 반복문을 실행해야하므로 N번의 실행이 필요하고 S 인덱스 각각에서 P의 길이 M만큼의 검사를 거쳐야 하므로 최종적으로 시간복잡도는 \(O(N*M)\) 로 계산됩니다.

더 빠른 방법, KMP

이보다 빠르게, 고작 \(O(N+M)\)의 시간복잡도로 S에서 P를 찾아낼 수 있는 방법이 있습니다. KMP(Knuth–Morris–Pratt) 알고리즘이 바로 그것입니다. KMP 알고리즘의 기본 아이디어는 패턴을 찾기 위해 수행한 비교연산에서 얻은 정보를 활용하는 것입니다.

KMP 알고리즘을 위해서는 접두사(prefix)와 접미사(suffix), 그리고 이들을 비교하여 작성되는 Pi 배열에 대해 이해하고 있어야 합니다.

Prefix, Suffix, Pi

위에서 예로 들었던 P (ABCDABD)를 예로 들어보겠습니다.

먼저 접두사는 앞에서부터 시작해서 만들 수 있는 문자열의 부분, 반대로 접미사는 뒤에서 시작해서 만들 수 있는 문자열의 부분을 의미합니다.

따라서 ABCDABD의 접미사와 접두사는 아래와 같습니다.

Pi 배열은 이러한 개념을 이용하여 만들어지는 배열입니다. 정의는 아래와 같습니다.

Pi[i] = 문자열 인덱스 0~i로 만들어진 부분 문자열(P[0~i]) 중에서 prefix와 suffix가 같은 경우 중 길이의 최댓값, 단 prefix/suffix가 P[0~i]와 같은 경우는 제외

P (ABCDABD)에 대해서 Pi 배열이 만들어지는 과정을 확인하면 아래와 같습니다.

Pi배열의 정의에 의해 Pi[0]은 항상 0으로 고정됩니다. 그리고 Pi[1]부터 표에서 보이는 비교를 통해 조건을 만족하는 경우 중 길이가 최댓값인 경우를 Pi 배열로 저장합니다.

P (ababa)를 가지고 Pi배열을 다시 생성해보겠습니다.

비교에 의해 발생한 정보를 활용하는 방법

문자열 S(ABCDABCDABEE)에서 패턴 P(ABCDABE)를 찾는다고 가정해보겠습니다. 참고로, 패턴 P의 Pi 배열은 아래와 같습니다.

문자열 S의 인덱스 0에서 비교를 수행할 때 우리가 얻는 정보는 아래의 일치 행과 같습니다.

이 정보를 이용한다면, 다음 S에서 검색해야할 인덱스는 1이 아니라 4가 됩니다. 즉, 인덱스 1~3을 시작으로 하는 케이스는 검색할 필요도 없다는 정보를 얻을 수 있습니다. 이는 Pi 배열의 값을 이용했기 때문입니다. 이러한 사고의 흐름은 아래와 같습니다.

1. 패턴 P의 인덱스 5까지 일치함을 확인하였고, 인덱스 6에서 불일치가 발생했습니다 (현재 인덱스 = 6).

2. 지금까지 일치한 P의 부분배열 P[0~5] = ABCDAB는 prefix과 suffix가 일치하는 최댓값 길이는 2(ABCDAB)입니다.(이는 Pi[5]=2 로 바로 확인됩니다)

   1. 패턴 P는 연속으로 일치하는 5개로 이루어진 부분배열(ABCDAB)의 suffix(ABCDAB)의 다음 인덱스부터 검색을 시작해야합니다.
   2. 왜냐하면 prefix = suffix이므로 S[4~5] (P[0~5]의 suffix)는 반드시 P[0~1] (P[0~5]의 prefix)와 같음을 알고 있기 때문입니다.
   3. 따라서, P[2~6], S[6~10]을 비교하게 됩니다.

3. 이는 P와 일치하는 배열을 찾기 위해서는 S에서 AB로 시작하는 인덱스에서 시작해야하기 때문이며, S[1]~S[3]은 AB로 시작하지 않음을 인덱스 0에서의 비교를 통해 이미 습득했기 때문입니다.

   1. S[1~2]=AB, S[2~3]=AB, S[3~4]=AB인 경우에는 일치 비교 결과가 현재와는 다를 것입니다.

   2. index	0	1	2	3	4	5	6
      P	A	B	C	D	A	B	E
      IF S[1]=A	A(O)	B->A(X)	C->B(X)	D(O)	A(O)	B(O)	C(X)
      IF S[2]=A	A(O)	B(O)	C->A(X)	D->B(X)	A(O)	B(O)	C(O)
      IF S[3]=A	A(O)	B(O)	C(O)	D->A(X)	A->B(X)	B(O)	C(O)

이러한 정보들을 종합해보았을 때, 아래와 같이 인덱스 6번부터 5번의 추가 비교가 이루어지고 S에서 P를 찾게됩니다.

KMP 알고리즘을 이용한 Pi 배열 생성

KMP 알고리즘을 적용하여 문자열을 빠르게 탐색하기 위해서는 미리 Pi 배열을 생성해놓아야합니다. 그러나 1) 각 부분배열에 대해 2) 모든 prefix와 suffix를 찾고 3) 비교하여 길이가 최대인 경우를 찾는 방법은 시간복잡도가 꽤 큽니다(\(O(m * m * m)\)).

패턴 P를 스스로와 비교하는 KMP 알고리즘을 통해 $ O(m) $ 시간복잡도로 Pi 배열을 생성할 수 있습니다.

예를 들어, P(ABCDABEA)에 대해서 KMP 알고리즘을 적용하여 Pi 배열을 만드는 과정을 살펴보겠습니다.

먼저, P[0]은 항상 0으로 시작합니다.

P_의 인덱스를 1 이동시키고, 1번 인덱스를 비교합니다. P[1] != P_[0]을 확인했으므로, Pi[1] = 0 을 입력합니다.

다시, P_의 인덱스를 1 이동시킵니다. 여전히 P[2] != P_[0] 이므로 Pi[2 ] = 0 을 입력합니다.

P_의 시작 인덱스가 4가 될 때까지 겹치는 부분이 없으므로 생략하고 넘어가겠습니다.

이제 P_는 인덱스 4부터 시작합니다. P[4] = P_[0] 으로 일치하므로 Pi[4] = 1을 입력합니다.

이전 비교에서 일치했으므로 P_를 이동시키지 않습니다. 그리고 P[5] = P_[1] 으로 일치합니다. 단, Pi[4] = 1이므로, Pi[5] = Pi[4] + 1을 입력합니다.

이전 비교에서 일치했으므로 P_를 이동시키지 않습니다. 그러나, P[6] != P_[2]이라서, Pi[6]=0을 입력합니다.

이전 비교가 불일치했으므로, P_ 배열을 이동시켜야합니다. P[7]과 P_[0]이 비교될 수 있도록 배열을 이동시킵니다. P[7] = P_[0]이므로 Pi[7]=1을 입력하고 비교가 종료됩니다.

Code

아래 코드는 1786 찾기의 풀이입니다.

import sys

T = sys.stdin.readline().rstrip()
P = sys.stdin.readline().rstrip()

def getPi(P) :
    m = len(P)
    j = 0
    pi = [0 for _ in range(m+1)]
    for i in range(1, m) :
        while (j > 0 and P[i] != P[j]):
            j = pi[j-1]
        if P[i] == P[j] :
            j += 1
            pi[i] = j
    return pi

pi = getPi(P)

def KMP(T, P) : 
    answer = {"count" : 0 ,
             "index" : []}
    n = len(T)
    m = len(P)
    j = 0
    for i in range(n) :  # String Index는 계속 진행
        while (j > 0 and T[i] != P[j]): # Pattern Index를 결정하는 코드 블록
            j = pi[j-1] # Prefix = Suffix인 인덱스의 다음 인덱스 (pi[j-1]가 개수이기 때문에 다음 인덱스 역할)
        if T[i] == P[j]:
            if j == m-1 : # Pattern을 발견함
                answer['count'] += 1
                answer['index'].append(i-m+1)
                j = pi[j] # Pattern Index 결정
            else :
                j += 1
    return answer

answer = KMP(T, P)

print(answer['count'])
print(' '.join(list(map(lambda x : str(x+1), answer['index']))))