使用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;
}