使用C++進行字元串查找

一、字元匹配演算法

在實現字元串查找中，字元匹配演算法是最基本的一種演算法。字元匹配演算法的思路是，我們將目標字元串的前綴和要查找的子串進行一一對比，如果相同，就繼續對比兩個字元串的下一個字元，如果不同，則對比目標字元串中的下一個子串。通過這種方式，我們能夠準確地找到要查找的子串在目標字元串中的位置。

下面是字元匹配演算法的代碼示例：

int findString(const string& targetStr, const string& toFind) {
    int len1 = targetStr.size(), len2 = toFind.size();
    for(int i = 0; i < len1 - len2 + 1; ++i) {
        int j = 0;
        for(; j < len2; ++j) {
            if(targetStr[i+j] != toFind[j]) break;
        }
        if(j == len2) return i;
    }
    return -1;
}

二、KMP演算法

字元匹配演算法的時間複雜度為O(mn)，其中m為目標字元串長度，n為要查找的子串長度。而KMP演算法通過一個預處理過程，先將要查找的子串轉化成一個”部分匹配表”，然後在匹配的過程中利用這個表來盡量減少比較次數，從而達到O(m+n)的時間複雜度。

下面是KMP演算法的代碼示例：

int* getPartialMatchTable(const string& toFind) {
    int len = toFind.size();
    int* table = new int[len];
    table[0] = 0;
    for(int i = 1, j = 0; i  0 && toFind[i] != toFind[j]) j = table[j-1];
        if(toFind[i] == toFind[j]) ++j;
        table[i] = j;
    }
    return table;
}

int findStringKMP(const string& targetStr, const string& toFind) {
    int len1 = targetStr.size(), len2 = toFind.size();
    int* table = getPartialMatchTable(toFind);
    for(int i = 0, j = 0; i  0 && targetStr[i] != toFind[j]) j = table[j-1];
        if(targetStr[i] == toFind[j]) ++j;
        if(j == len2) return i - len2 + 1;
    }
    delete[] table;
    return -1;
}

三、Boyer-Moore演算法

Boyer-Moore演算法針對字元匹配演算法的缺點，採用了兩個啟發式的策略：壞字元規則和好後綴規則。壞字元規則指的是利用要查找的子串中的不匹配字元來儘可能地跳過比較，而好後綴規則利用目標字元串中已經匹配的後綴串和子串前綴來尋找不匹配的字元。

下面是Boyer-Moore演算法的代碼示例：

int findStringBM(const string& targetStr, const string& toFind) {
    int len1 = targetStr.size(), len2 = toFind.size();
    if(len2 == 0) return 0;
    int* skip = new int[256];
    for(int i = 0; i < 256; ++i) skip[i] = len2;
    for(int i = 0; i < len2 - 1; ++i) skip[toFind[i]] = len2 - i - 1;
    for(int i = 0; i = 0 && targetStr[i+j] == toFind[j]; --j);
        if(j == -1) {
            delete[] skip;
            return i;
        }
        i += max(skip[targetStr[i+j]], len2 - j - 1);
    }
    delete[] skip;
    return -1;
}

四、Rabin-Karp演算法

Rabin-Karp演算法是利用哈希函數的思路來進行字元串查找的演算法。通過預處理目標字元串中每個子串的hash值，然後與要查找的子串的hash值比較，從而實現快速查找。不過由於哈希函數的限制，這種演算法並不適用於所有的字元串查找場景。

下面是Rabin-Karp演算法的代碼示例：

int findStringRK(const string& targetStr, const string& toFind) {
    int len1 = targetStr.size(), len2 = toFind.size();
    if(len2 == 0) return 0;
    const int base = 26;
    long long toFindHash = 0;
    for(int i = 0; i < len2; ++i) toFindHash = toFindHash * base + toFind[i];
    long long targetHash = 0;
    for(int i = 0; i = len2) targetHash -= targetStr[i-len2] * pow(base, len2);
        if(targetHash == toFindHash && targetStr.substr(i-len2+1,len2) == toFind) return i - len2 + 1;
    }
    return -1;
}