[알고리즘 문제 해결 전략] Chapter 20. 문자열

문자열 검색 문제를 위한 KMP 알고리즘과 자료 구조
접미사 배열(suffix array)을 알아보고, 이들로 해결할 수 있는 문제의 예를 살펴보자.

 

 

용어 정리

• 문자열 S의 i번 글자부터 j번 글자까지로 구성된 문자열을 S의 부분 문자열(substring)이라 부르고, S[i...j]로 표기
• 문자열 S의 0번 글자부터 a번 글자까지로 구성된 부분 문자열 S[0...a]를 S의 접두사(prefix)라고 부르고, S[...a]로 표기
• 문자열 S의 b번 글자부터 끝까지로 구성된 부분 문자열 S[b...|S|-1]을 S의 접미사(suffix)라고 부르며, S[b...]로 표기

 

문자열 검색

• 문자열 검색 문제: 주어진 긴 '짚더미(haystack)' 문자열 H가 '바늘(needle)' 문자열 N을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제
• 다음은 이를 단순하게 구현한 예시이다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> naiveSearch(const string& H, const string& N) {
    vector<int> ret;

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

• 입력이 큰 경우 비효율적일 수 있지만, 이 경우는 흔치 않고 구현이 단순하다는 장점
• C의 strstr(), C++의 string::find(), 자바 문자열의 indexOf()에 구현되어있음

 

KMP 알고리즘

 일반적인 문자열 검색 알고리즘에서 중복되는 부분을 스킵하여 성능을 향상시킨 알고리

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> getPartialMatch(const string& pattern) {
    int patternSize = pattern.size();
    vector<int> table(patternSize, 0);

    int j = 0;
    for(int i = 1; i < patternSize; i++) {
        //j를 i번째와 j번째가 일치하지 않을 때 j를 한 칸 back
        while(j > 0 && pattern[i] != pattern[j]) {
            j = table[j-1];
        }
        if(pattern[i] == pattern[j]) {
            table[i] = j++;
        }
    }
    return table;
}

//haystack H의 부분 문자열로 needle N이 출현하는 시작 위치들을 모두 반환한다.
vector<int> kmpSearch(const string& H, const string& N) {
    int n = H.size(), m = N.size();
    vector<int> ret;

    //pi[i] = N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이
    vector<int> pi = getPartialMatch(N);

    //begin = matched = 0에서부터 시작
    int begin = 0, matched = 0;
    while(begin <= n - m) {
        //haystack의 해당 글자가 needle의 해당 글자와 같다면
        if(matched < m && H[begin + matched] == N[matched]) {
            matched++;
            //m글자가 모두 일치하면 답에 추가
            if(matched == m) {
                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;
}

 

>> 추후 완성 예정

---

참고자료

• 구종만, < 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 >, 인사이트, 2012.11.01
• https://www.youtube.com/watch?v=yWWbLrV4PZ8