KMP 알고리즘

네이버에나 한글 문서등에서 찾기를 사용하면 긴 문서안에서 우리가 원하는 단어가 어디서 등장하는지 쉽게 찾을 수 있다. ABCABC에서 BC라는 문자를 찾고자 할 때는 다음과 같이 진행할 수 있다.

이런식으로 계속 BC를 옮겨가면서 일치하는지 여부를 확인하는 작업은 문자열의 길이를 N, 단어의 길이를 M이라고 했을 때 O(NM) 의 시간이 걸리게 된다. 만약 문서의 크기가 작다면 문제가 없지만 실생활에서 사용하기에는 매우 느려서 사용하기 어렵다. 이제 우리는 O(N+M) 의 시간만에 해결하게 해주는 KMP 알고리즘을 알아볼 것이다.

1. Suffix & Prefix

Suffix란 접미사, Prefix란 접두사를 의미하는 것이다.
예를 들어 ABCAB에 대해 접미사와 접두사를 구해보자.
-Suffix
B
AB
CAB
BCAB
ABCAB

-Prefix
A
AB
ABC
ABCA
ABCAB

2. Pi 배열 (실패 함수)

문자열의 0~i까지의 부분 문자열에 대해서 prefix와 suffix가 같은 지점의 길이를 나타내주는 배열이다. 단 prefix가 자기 자신이 되는 것은 제외한다.
예를들어 ABCABD의 Pi 배열을 나타내보자.

3. KMP

만약 ABCABCABD 라는 문자열에서 ABCABD라는 문자를 찾고자한다고 하자.

하나하나 매칭을 하다보면 마지막 C와 D가 일치하지 않는다는 것을 확인할 수 있다. 하지만 위에서 보았듯이 일일히 문자를 옮겨가면서 매칭을 하는 것은 비효율 적이라는 것을 배웠다. 따라서 틀렸던 부분인 C부터 새롭게 확인을 해나가고 싶다. 문자 ABCABD에서 일치하지 않는 부분인 D를 제외하고 ABCAB를 살펴보자.

AB라는 문자가 앞에서도 나타나고 뒤에서도 나타나는데 이를 활용하면 AB라는 문자는 중복해서 나타나기때문에 ABCABD를 비교하던 것을 ABC를 비교하는 차례로 단축시킬 수 있다.

이는 pi 배열에서 구한 prefix = suffix 인 부분의 길이와도 같다. 새롭게 비교를 해서 구한 결과는 아래와 같고 문자열 속에서 원하는 문자를 찾아냈다.

이제 KMP를 구현을 해보자. 문자열 T와 찾아낼 문자인 P가 존재한다고 하자. i와 j는 각각 T와 P에서의 index를 의미한다. 만약 T의 index 3부터 P가 존재하는지를 찾고 있을 때 P에서 index 2인 C를 비교할 차례라고 하면 그림은 다음과 같이 되고 i의 값은 3 j의 값은 2가 된다. 추가로 T에서 P와 비교해야할 위치는 i+j인 5가 되는 것을 확인할 수 있다.

그렇다면 다음과 같이 i = 0, j = 5인 상황을 살펴보자.

T와 P의 Character가 일치하지 않기 때문에 우리는 i와 j 값을 이동시켜줘야 한다. 이 때 j는 위에서 알아봤듯이 Pi[j-1] = Pi[4] = 2 이 된다는 것을 알 수 있고 i는 기존 5에서 새로워진 j를 뺀 위치로 이동한다는 것을 알 수 있다. 따라서 j는 2로 변하고 i는 5-2 = 3 이 된다.

pi배열을 위에서 실패 함수라고 부르는 이유가 바로 이것이다. 문자 비교가 실패했을 경우 이동해야할 위치를 나타내주는 역할을 하기 때문이다.

그 후 새롭게 변한 i와 j를 갖고 T와 P의 Character가 일치하는지 여부를 다시 확인한다. 일치하게 된다면 j 값을 증가시키면 되고 아닐 경우 j가 0이 될때까지 위의 과정을 반복한다. j가 0이 된다면 더 이상 이전 정보를 활용할 수 없다는 뜻이 되고 i를 1 증가시켜 새로운 비교를 해나간다.

• KMP Code

var i = 0, j = 0
var resultIndex = [String]()
while i + j < T.count {
    let Curr = i+j
    while j > 0 && T[Curr] != P[j] {
    //j가 0이 되거나 T와 P의 Character가 일치할때까지
        j = pi[j-1]
        i = Curr - j
    }
    if T[Curr] == P[j] {
    //일치시 j += 1
        j += 1
    }
    else {
    //j가 0이여서 더이상 이전 정보를 활용할 수 없을 때 i += 1
        i += 1
    }
    if j == P.count {
        resultIndex.append("\(i+1)")
        j = pi[j-1]
        i = Curr - j + 1
    }
}

4. MakePi

그렇다면 Pi함수는 어떻게 만들면 좋을까? 모든 i에 대해서 앞과 뒤를 비교해가며 구할 수도 있겠지만 KMP와 비슷한 과정이라는 것을 알고 KMP알고리즘을 활용하면 간단하다. T라는 문자열 대신 P속에서 P를 매칭시키는 방법을 사용하도록 하자.

• makePi Function

func makePi(str: [Character]) {
    var j = 0
    for i in 1..<str.count {
        while j > 0 && str[i] != str[j] {
            j = pi[j-1]
        }
        if str[i] == str[j] {
            j += 1
            pi[i] = j
        }
    }
}

함수를 보면 알겠지만 KMP알고리즘과 모습이 상당히 유사하다. 유의할 점은 주어진 i는 움직이지 않고 j값만을 이동시켜가며 pi를 구한다는 것이다. ABABDABABA 라는 P가 주어진다고 하자. 이 때 pi값을 하나하나 만들어가면 다음과 같고 마지막 pi값을 구하려한다 하자.

D와 A는 일치하지 않기 때문에 j값을 4에서 pi[4-1] = 2 로 변경시키자. 이것의 의미는 ABAB는 AB가 중복되기 때문에 ABABD를 비교하던 차례에서 ABA를 비교하는 차례로 넘어가야 한다는 것이다.

이제 A로 두 문자가 일치하기 때문에 Pi[9] = 3이 된다.

추천 문제

백준 4354 문자열 제곱
백준 1305 광고
백준 10266 시계 사진들