문자열 일치 알고리즘 및 C++ 구현

C++ 프로그래밍에서는 문자열 일치 문제가 매우 일반적입니다. 간단히 말하면, 문자열 매칭 문제는 텍스트 문자열에서 특정 패턴 문자열을 찾는 과정입니다. 실제 응용 분야에서 문자열 매칭 알고리즘은 주로 텍스트 검색, 이미지 인식, 자연어 처리 등의 분야에서 사용됩니다. 이 기사에서는 일반적으로 사용되는 문자열 일치 알고리즘과 C++에서의 구현에 중점을 둘 것입니다.

1. 순진한 문자열 일치 알고리즘

순진한 문자열 일치 알고리즘은 무차별 검색 일치 알고리즘이라고도 합니다. 일치하는 위치를 찾거나 전체 T에 P가 존재하지 않을 때까지 텍스트 문자열 T의 각 위치에서 패턴 문자열 P를 연속적으로 일치시키려는 아이디어입니다. 이 알고리즘의 시간 복잡도는 O(n*m)로 높습니다. 여기서 n과 m은 각각 텍스트 문자열 T와 패턴 문자열 P의 길이입니다.

C++ 코드는 다음과 같이 구현됩니다.

void naive_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    for(int i = 0; i <= n-m; i++) {
        int j;
        for(j = 0; j < m; j++) {
            if(T[i+j] != P[j]) break;
        }
        if(j == m) {
            cout << "Pattern occurs with shift " << i << endl;
        }
    }
}

2. KMP 문자열 일치 알고리즘

KMP 문자열 일치 알고리즘의 핵심 아이디어는 패턴 문자열 P 공통 접두사의 가장 긴 접두사와 접미사를 일치시키는 것입니다. 텍스트 문자열 T에서 이미 일치하는 문자의 반복 일치를 피하기 위해 일치에 및 접미사가 사용됩니다. 이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 텍스트 문자열의 길이입니다.

C++ 코드는 다음과 같이 구현됩니다.

void get_next(string P, vector<int>& next) {
    int m = P.length();
    next[0] = -1;
    int i = 0;
    int j = -1;
    while(i < m) {
        if(j == -1 || P[i] == P[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

void kmp_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    vector<int> next(m+1);
    get_next(P, next);
    int i = 0;
    int j = 0;
    while(i < n) {
        if(j == -1 || T[i] == P[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        if(j == m) {
            cout << "Pattern occurs with shift " << i-m << endl;
            j = next[j];
        }
    }
}

3. BM 문자열 일치 알고리즘

BM 알고리즘은 잘못된 문자와 좋은 접미사 규칙을 기반으로 하는 문자열 일치 알고리즘입니다. 핵심 아이디어는 패턴 문자열 P의 마지막 문자를 일치시키고 텍스트 문자열 T에서 일치하지 않는 문자를 전처리하여 일치하는 문자를 건너뛰는 것입니다. 이 알고리즘의 시간 복잡도는 O(n)입니다.

C++ 코드는 다음과 같이 구현됩니다.

const int MAXCHAR = 256;

void bm_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    vector<int> badchar(MAXCHAR, -1);
    for(int i = 0; i < m; i++) {
        badchar[int(P[i])] = i;
    }
    vector<int> suffix(m+1);
    vector<bool> prefix(m+1);
    get_suffix_prefix(P, suffix, prefix);
    int i = 0;
    while(i <= n-m) {
        int j = m-1;
        while(j >= 0 && P[j] == T[i+j]) j--;
        if(j < 0) {
            cout << "Pattern occurs with shift " << i << endl;
            i += (i+m < n) ? m-badchar[int(T[i+m])] : 1;
        } else {
            i += max(suffix[j+1], j-badchar[int(T[i+j])]);
        }
    }
}

이 글에서는 주로 일반적으로 사용되는 문자열 매칭 알고리즘과 이를 C++로 구현하는 방법을 소개합니다. 순진한 문자열 매칭 알고리즘은 단순하지만 시간 복잡도가 높은 반면, KMP 및 BM 알고리즘은 매칭 위치를 더 빨리 찾을 수 있습니다. 그 중 KMP 알고리즘은 짧은 패턴 문자열에 적합하고, BM 알고리즘은 긴 패턴 문자열에 적합합니다. 실제 애플리케이션에서는 다양한 상황에 따라 적절한 문자열 일치 알고리즘을 선택해야 합니다.

위 내용은 문자열 일치 알고리즘 및 C++ 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!