KMP(Knuth-Morris-Pratt) / 문자열 매칭

※ 이 게시물은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 2 - 구종만>에 나오는 KMP부분을 읽고 개인이 정리하는 글입니다. 더 자세한 설명은 위의 책에 나와있습니다.

 

KMP알고리즘은 아주 긴 문자열 $S_{1}$과 $S_{2}$가 주어졌을 때, $S_{1}$속에 $S_{2}$가 몇 번이나 등장하는지 빠르게 알아낼 수 있는 알고리즘이다.

 

두 문자열을 비교할 때, 가장 쉬운 방법은 $S_{1}$의 모든 index를 순회하면서, $S_{2}$의 길이만큼 서로 문자 같은지 비교를 진행하는 것이다. 하지만 이럴 경우 총 ($S_{1}.length-S_{2}.length + 1) \times S_{2}.length$만큼 비교를 진행해야 한다. 하지만, 구현이 단순하다는 장점이 존재한다. 이 장점 때문에 C에서는 strstr(), C++에서 string:find(),  java에서는 indexOf()는 지금 말한 방법을 사용한다.

---

KMP도 위의 방법을 기반하여 낭비하고 있는 정보를 활용한다. 여기서 낭비하고 있는 정보는 어떤 문자열을 비교할 때, 일치하였다는 정보이다. 추가로 하나, 접두사와 접미사를 이용한다. 어떤 문자열 $S = ananaana$가 있다고 하자.

그렇다면 다음과 같이 접두사와 접미사가 일치하는 길이를 표현하는 표를 만들 수 있다. 위에서 만든 접두사 테이블을 여기서는 pi테이블 이라고 한다.

문자열 "ananaana"의 접두사, 접미사 테이블

KMP알고리즘에서 문자열을 비교할 때, 시작위치 $begin$을 설정하고, $matched$만큼 문자열이 일치하고 다음에 불일치했다면, 다음 문자열 비교 시작점 위치를 $matched - pi[matched-1]$로 이동한다. 추가로 $pi[matched-1]$만큼 일치하였기 때문에, $matched$값도 $pi[matched-1]$로 업데이트한다.

 

begin의 이동과 matched의 변화

처음 $begin1$위치에서 비교를 시작하면 $matched=5$에서 비교가 종료된다. 이후, $begin1$위치를 $matched - pi[matched-1] = 5 - pi[4] = 5 - 3 = 2$만큼 추가로 이동시킨다. 따라서 $begin2$의 위치로 이동이 된다. 하지만 일치한 값이 0이라면, 어쩔 수 없이 다음 인덱스로 넘어가서 탐색을 진행한다. 지금까지의 부분을 C++ 코드로 구현을 하면 다음과 같다.

 

// haystack에서 needle을 찾은 시작점의 위치들을 반환한다.
vector<int> kmpSearch(string haystack, string needle) {
    int n = haystack.length();
    int m = needle.length();

    // begin은 haystack에서 비교를 시작하는 위치를 나타낸다.
    // matched는 begin에서 시작을 했을 때, 얼마만큼 일치를 했는지 표현한다.
    int begin = 0, matched = 0;

    // pi[x] = needle의 [0, x]부분 문자열 중, 접두사와 접미사가 일치하는 최대 길이
    vector<int> pi = getPI(needle);
    vector<int> ret;

    // haystack에서 needle을 찾는 것이므로, haystack시작점이 n - m 이상일 수 없다.
    while (begin <= n - m) {

        // 1. matched의 길이가 needle의 길이(본인)보다 작아야 한다.
        // 2. 두 인덱스를 비교하였을 때, 일치해야 matched가 증가된다.
        if (matched < m && haystack[begin + matched] == needle[matched]) {
            ++matched;
            if (matched == m) ret.push_back(begin);
        } else {
            // 문자열을 탐색했을 때, 부분일치된 곳이 없다면 
            // 어쩔 수 없이 건너뛰지 못하고 바로 다음 인덱스부터 탐색한다.
            if (matched == 0) ++begin;
            // 문자열 탐색 중 부분적으로 일치된 곳이 존재한다면
            // 이미 알아낸 정보를 이용하여, 찾을 다음 시작점으로 빠르게 넘어간다.
            else {
                // 1. 시작점 = 시작점 + 일치한 길이 - 접두사와 접미사가 일치하는 최대 길이
                //    matched만큼 일치했다는 것은 실제 문자열에서는 [0 ... matched-1]까지 일치
                // 2. 동시에, 그 최대 길이만큼 일치했다고 표현.
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }

    return ret;
}

---

이제 pi배열을 구하는 함수를 구현해야 하는데 이번에도 KMP를 사용하여 구현한다. $S_{2}$에서 $S_{2}$를 찾는 방식이다. 다만, $begin$을 처음에 0으로 설정하게 되면 자기 자신을 찾게 되므로 1부터 시작한다.

vector<int> getPI(string needle) {
    int n = needle.length();
    vector<int> pi(n, 0);
    int begin = 1, matched = 0;

    while (begin + matched < n) {
        if (needle[begin + matched] == needle[matched]) {
            ++matched;
            pi[begin + matched - 1] = matched;
        } else {
            if (matched == 0) ++begin;
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }

    return pi;
}