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