[종만북] 문자열 검색 - KMP 알고리즘 / 문자열

[종만북] 문자열 검색 - KMP 알고리즘 / 문자열

[종만북] 문자열 검색 - KMP 알고리즘 / 문자열

 

문자열 검색 - KMP 알고리즘

단순한 알고리즘의 검색 과정에서 얻는정보를 이용하여 시간을 절약 할 수 있다.
H 의 부분 문자열을 N 과 비교 시, N 의 첫 글자와 대응 되지 않는 H 의 부분문자열 위치를 시작 위치 후보들에서 제외 시키는 방법으로 구현하면 최적화가 가능하다.

이와 같은 방법은 커누스-모리스-프랫(Knuth-Morris-Pratt) 알고리즘이며, 흔히 KMP 알고리즘으로 부른다.

• H[i...i+matched-1] =  N[...matched-1](접두사) 이 일치 할때,
  
  • i < i+k < matched-1,
    
    • H[i+k...i+matched-1] = N[K...] (접미사) 가 일치 한다면,
    • N[K...] (접미사) = N[...matched-1] (접두사) 구간이 존재
      • N의 접미사 구간과 접두사 구간이 같은 문자열인 경우
    • 이를 이용하기 위하여 N의 각 접두사에 대해 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산해 둔다.

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

      • 부분 일치 테이블
  • 정리
    • i+k 시작점에서 일치 시, N[...matched-1] 의 문자열에서 길이가 matched-k 인" 접두사 = 접미사" 구간이 존재 해야함.
    • N의 각 접두사에 대해 "접두사 = 접미사" 최대 길이를 계산해두고 이 길이만 비교하여 최적화 가능
      • pi[i] = N[...i] 의 "접두사 = 접미사" 문자열 최대 길이
      • pi[i] 를 이용하여 다음 시작위치를 계산

 

 

KMP 알고리즘 구현

// KMP 문자열 검색 알고리즘의 구현

// H 의 부분 문자열로 N 이 출현하는 시작 위치들을 모두 반환
vector <int> kmpSearch(const string& H, const string& N){
    int h_length = H.size()
    int n_length = N.size();
    
    vertor<int> ret;
    
    // pi[i] = N[...i] 의 접미사도 되고 접두사도 되는 문자열의 최대 길이
    vector<int> pi = getPartialMatch(h_length);
    
    // begin = matched = 0 에서부터 시작
    int begin = 0;
    int matched = 0;
    
    while(begin <= h_length - n_length){
        // H 의 해당 글자가 N 의 해당 글자와 같다면
        if(matched < m && H[begin + matched] == N[matched]){
            ++matched;
            // n_length 개의 글자가 모두 일치하면 답에 추가.
            if(matched == n_length) ret.push_back(begin);
        } else {
            // 예외: matched 가 0 인 경우, 다음칸에서 시작
            if(matched == 0){
                ++begin;
            } else {
                begin += matched - pi[matched-1];
                // begin 을 옮겻다고 처음부터 비교할 필요가 없다.
                // 옮긴 후에도 pi[matched-1] 만큼은 항상 일치 하기 때문
              	matched = pi[matched-1];
            }
        }
    }
    return ret;
{

• 시작위치 0 에서부터 H 와 N 의 글자를 비교
• matched 글자가 일치한 후 불일치가 발생한 경우, 시작위치를 matched-pi[matched-1] 만큼 증가
  • pi[i] = N[...i] 의 "접두사 = 접미사" 문자열의 최대 길이
  • pi[] 는 N 이 어디까지 일치했는지가 주어질 때, 다음 시작 위치를 알려주기 때문에 부분 일치 테이블 (Partial match table) 이라고 한다.

 

 

시간 복잡도 분석

• while문 내에서 begin + matched 의 값은 절대 감소하지 않음
  • matched 가 감소할 때에도 begin은 항상 감소분만큼 증가하기 때문에, begin+matched 는 불변
• 문자 비교 분기
  • 문자 비교 성공 - H 의 각 문자당 최대 한 번씩만 발생 가능 -> 최대 O(|H|) 번 수행
  • 문자 비교 실패 - 0 <= begin <= |H| - |N|, 분기당 1 씩 증가 -> 최대 O(|H|) 번 수행
• 전체 수행 회수: 최대 O(|H|) 번 수행, H 의 길이에 비례

 

 

부분 일치 테이블 구현

• 간단한 방법
  • N 의 각 접두사에 대해 가능한 답을 하나씩 모두 시도
  • |N| 개의 모든 접두사에 대해 O(|N| ^ 3) 의 수행

// N 에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용하여 pi[] 를 계산
// p[i] = N[...i] 의 "접미사 = 접두사" 인 문자열의 최대 길이

vector<int> getPartialMatchNaive(const string& N){
    int n_length = N.size()
    vector<int> pi(n_length, 0);
    
    // 단순한 문자열 검색 알고리즘 구현
    for (int begin = 1; begin < n_length; ++begin){
        for (int i = 0; i < m; ++i){
            if(N[begin + i] != N[i]) break;
        
            // i+1 글자가 서로 대응
            pi[begin + i] = max( pi[begin + i] , i + 1 );
        }
    }
    return pi;
}

 

 

• 최적화
  • 각 접두사에 대해 pi[] 의 값을 모든 접두사에 대해 계산
  • N[i] 와 N[begin + i] 가 일치할 때마다, pi[begin+i] 를 갱신
  • |N| 개의 모든 접두사에 대해 O(|N| ^ 2) 의 수행

// KMP 알고리즘올 이용해 부분 일치 테이볼을 생성하기
// N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi[]를 계산
// pi[i] = N[...i] "접미사 = 접두사" 문자열의 최대 길이

vector<int> getPartiaLMatch(const string& N) {
    int n_length = N.size();
    vector<int> pi(n_length, 0);
    
    // KMP 이용
    
    // N을 N에서 찾는다. begin = 0 인 경우 자기자신을 찾는 경우라서 제외
    int begin =1, matched =0;
    
    // 비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록
    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|)
• 따라서, KMP를 이용한 부분 문자열 검색의 전체 시간복잡도는 O(INI +IHI)