[Algorithm] KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)

문자열 검색

문자열 검색 문제는 문자열 H가 주어졌을 때 문자열 N을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제다.

이 문제를 풀 수 있는 가장 간단한 방법은 H의 가능한 모든 위치에서 다 시도해보는 방법이다. H의 각 위치의 부분 문자열이 N과 일치하는지 일일히 다 확인하는 것이다.

시작 위치의 수는 O(∣H∣)가 되고, 각각 비교에 걸리는 시간은 O(∣N∣)이 걸리기 때문에, 총 걸리는 시간은 O(∣H∣∣N∣)이다.

C의 strstr(), C++의 string::find(), 자바의 indexOf(), 자바스크립트의 String.prototype.indexOf() 등 대부분 표준 라이브러리에서 사용된다.

 

KMP(Knuth-Morris-Pratt) 알고리즘

더 빠르게 할 수는 없을까?

위에서 본 방법은 간단하지만 최선의 방법은 아니다. 검색 과정에서 얻는 정보를 버리지 않고 활용하면 시간을 절약할 수 있다.

어떤 정보를 활용할 수 있을까? 어떤 긴 문자열 H에서 N="aabaabac"를 찾는다고 해보자.

어떤 시작 위치 i에서부터 N을 맞췄는데 첫 일곱 글자 "aabaaba"가 일치했지만 마지막 글자는 불일치했다. 이때, 단순한 알고리즘은 바로 다음 위치인 i + 1에서 매칭을 다시 시작할 것이다. 하지만 일곱 글자가 대응됐다는 사실을 통해 우리는 답이 될 가능성이 있는 다음 위치를 특정할 수 있다.

우리는 i부터 불일치한 위치 전까지는 H에 어떤 문자가 있는지 알 수 있다(...aabaaba...). 그렇기 때문에 다음 위치 i + 1에서 시작하면 N과 절대 일치할 수 없다는 사실을 알 수 있다. 왜냐하면 i + 1에서 시작하면 첫 두 글자가 "ab"인 것을 알고 있기 때문이다. i + 2의 경우도 마찬가지다. "b"로 시작하는 것을 알고 있기 때문에 일치할 수 없다.

이런 식으로 i + 6까지 대응해보면 답이 될 가능성이 있는 시작위치는 i + 3 (aaba...)과 i + 6 (a...) 밖에 없다는 것을 알 수 있다. 따라서 시작 위치를 i + 1이 아닌 i + 3부터 검색을 시작하면 된다. i에서 뿐만 아니라 어느 위치 x에서도 일곱 글자가 일치했다면 x + 3에서 시작하면 된다. 어느 위치에서도 일곱 글자가 일치하면 위에서 알아낸 정보는 똑같이 특정할 수 있기 때문이다.

즉, 불일치가 일어났을 때 지금까지 '일치한 글자 수'를 이용해 '다음 시작 위치'를 빠르게 알아낼 수 있다는 것이다.

일치한 글자 수는 항상 0에서 ∣N∣ 사이의 정수이기 때문에, 전처리 과정에서 이 정보들을 미리 계산해 저장해 사용할 수 있다.

이런 최적화를 사용한 방식이 바로 'KMP(Knuth-Morris-Pratt) 알고리즘'이다.

 

다음 시작 위치 찾기

위 예에서 i + k가 후보가 될 수 있기 위해서는 어떤 특징을 만족해야 할까?

i + k부터 i + 6의 글자는 "aabaaba"의 뒷부분에 해당하는 글자다. 시작 위치를 i + k로 옮겼을 때 이 글자는 "aabaaba"의 앞부분과 일치해야 후보가 될 수 있다.

예를 들어 k가 4라면, i + 4부터 i + 6까지 글자는 "aba"다. 이 글자는 "aabaaba"의 앞부분과 일치하지 않기 때문에 후보가 될 수 없다.

즉, m개 일치했을 때 시작 위치 i + k에서 답을 찾을 수 있기 위해서는 N[...m − 1]의 길이 m − k인 접두사(prefix)와 접미사(suffix)가 같아야 한다. i + 3의 경우 길이 7 − 3 = 4인 접두사는 "aaba"이고 접미사도 "aaba"이기 때문에 다음 시작 위치가 될 수 있다.

KMP 알고리즘은 전처리 과정에서 다음과 같이 정의되는 배열 pi를 계산한다.

• pi[i] : N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이

이 배열을 통해 어디까지 일치했는지 i가 주어졌을 때 다음 시작 위치를 알 수 있다. 이 배열을 흔히 '부분 일치 테이블'이라고 부른다.

예제의 부분 일치 테이블은 다음과 같다.

i	N[..i]	접두사이면서 접미사인 최대 문자열	pi[i]
0	a	-	0
1	aa	a	1
2	aab	-	0
3	aaba	a	1
4	aabaa	aa	2
5	aabaab	aab	3
6	aabaaba	aaba	4
7	aabaabac	-	0

 

구현

적절한 전처리 과정을 통해 pi를 계산했다고 치고 구현해보자. KMP 알고리즘 구현에서 고려해야 할 점은 다음과 같다.

• m글자 일치한 후 불일치가 발생했을 때 다음 시작 위치는 m - pi[m - 1] 만큼 증가시키면 된다.
• 시작 위치를 옮긴 후에는 첫 글자부터 대응할 필요 없이 pi[m - 1] 부터 확인하면 된다(접두사는 같은 것을 알기 때문).
• 답을 찾은 경우 후에는 불일치가 발생한 경우와 같이 다음 시작 위치에서부터 검색을 계속하면 된다.

function kmpSearch(H, N) {
    const ret = [];
    const pi = getPartialMatch(N);
    let begin = 0, matched = 0;
    
    while(begin <= H.length - N.length) {
        if (matched < N.length && H[begin + matched] === N[matched]) {
            // 모두 일치했다면 답에 추가한다.
            if (++matched === N.length ) ret.push(begin);
        }
        else {
            // 한 글자도 일치하지 않으면 다음 시작 위치에서 탐색한다.
            if(matched === 0) begin++;
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return ret;
}

 

부분 일치 테이블 생성하기

부분 일치 테이블을 생성하는 가장 간단한 방법은 N의 각 접두사에 대해 가능한 답을 하나씩 모두 시도하는 것이다. 하지만 이것은 O(∣N∣^3) 시간이 걸리기 때문에 비효율적이다.

대신 각 접두사의 pi를 따로 계산하는 것이 아닌 모든 접두사에 대해 계산함으로써 최적화할 수 있다.

function getPartialMatchNaive(N) {
    const pi = new Array(N.length).fill(0);
    for (let begin = 1; begin < N.length; begin++) {
        for (let i = 0; i + begin < N.length; i++) {
            if (N[begin + i] != N[i]) break;
            pi[begin + i] = Math.max(pi[begin + i], i + 1);
        }
    }
    return pi;
}

N="aabaabac"에서 자기 자신을 찾으면서, 두 글자 N[i] 와 N[begin + i] 가 같다면 pi[begin + i] 를 갱신해주면 된다.

여기서 검색 과정을 KMP 알고리즘으로 더욱 최적화 할 수 있다. 바로 이전 단계에서 얻은 pi 값을 사용하는 것이다.

function getPartialMatch(N) {
    const pi = new Array(N.length).fill(0);
    let begin = 1, matched = 0;
    
    while (begin + matched < N.length) {
        if (N[begin + matched] === N[matched]) {
            matched++;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched === 0) begin++;
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}

이렇게 구현한 전체 KMP 알고리즘의 시간 복잡도는 O(∣N∣ + ∣H∣)다.