[KMP] 문자열 알고리즘

KMP algorithm

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

문자열 검색, 짚더미(Haystack, H 문자열)에서 바늘(Needle, N 문자열)을 찾아봅시다!

불일치가 일어났을 때 지금까지 일치한 글자 수를 이용해 다음으로 시도해야 할 시작 위치를 빠르게 찾아냅니다.

 

필요한 것:

부분 일치 테이블(partial match table) p[i] 를 만듭니다.

 

pi[i]는 문자열 N[...i] (문자열 처음부터 i번째 까지 문자열)의 접두사도 되고 접미사도 되는 문자열의 최대 길이입니다.

예를들면 "aabaaba"에서 aaba는 접두사도 되고 접미사도 되는 최대 길이 문자열이므로,

pi[6] = 4 입니다.

 

KMP 알고리즘의 전체 반복문 수행 횟수는 O(|H|) 입니다.

 

 

#include <cstdio>
#include <vector>
#include <string>
using namespace std;

/*
    String search
    [strstr() in C], [string::find() in C++], [indexOf() in java] operated like below.
    O(|H||N|)
*/
vector<int> naive_search(const string &H, const string &N){
    vector<int> ret;

    for (int i = 0; i <= H.size() - N.size(); ++i){
        bool matched = true;
        for (int j=0; j<N.size(); ++j){
            if (H[i + j] != N[j]) {
                matched = false;
                break;
            }
        }
        if (matched) ret.emplace_back(i);
    }
    return ret;
}


vector<int> getPartialMatch(const string &N){
    int m = N.size();
    vector<int> pi(m, 0);

    int begin = 1, matched = 0;
    while(begin + matched < m){
        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;
}

// O(|N| + |H|)
vector<int> kmpSearch(const string &H, const string &N){
    int n = H.size(), m = N.size();
    vector<int> ret;

    /*
        pi[i] = N[...i]의 접두사와 접미사가 일치하는 최대 문자열의 길이
        O(N^3) --> O(N^2) --> O(|N|)

    */
    vector<int> pi = getPartialMatch(N);

    /* 
        begin은 N에서 시작 문자열 위치
        matched는 M에서 N과 현재까지 매치된 위치
    */
    int begin = 0, matched = 0;
    while(begin <= n - m){
        if (matched < m && H[begin + matched] == N[matched]){
            ++matched;
            if (matched == m) ret.emplace_back(begin); 
        }
        else {
            // 예외: matched가 0이면 다음 칸 부터 계속.
            if (matched == 0) ++begin;
            // KMP 핵심 logic
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return ret;
}

출처: 알고리즘 문제해결전략 2, 구종만