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中文網其他相關文章！