C++实现字符串匹配的两种算法，BF和KMP，给出例题和相关代码

在C++中，字符串匹配通常涉及两种经典算法：Brute Force (BF) 和 Knuth-Morris-Pratt (KMP) 算法。

**1. Brute Force (BF) - 滑动窗口搜索**
这种是最基础的暴力匹配方法，它逐字符遍历文本串，每遇到一个模式串的字符就检查下一个是否相等。如果所有字符都匹配，则认为找到一次匹配。这种方法的时间复杂度是O(nm)，其中n是文本串长度，m是模式串长度。

#include <iostream>
#include <string>

bool bruteForceMatch(const std::string& text, const std::string& pattern) {
    size_t i = 0, j = 0;
    while (i < text.size() && j < pattern.size()) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1; // 如果不匹配，从上一个匹配位置开始查找
            j = 0;         // 或者跳过已比较过的字符
        }
    }
    return j == pattern.size(); // 返回是否完全匹配
}

int main() {
    std::string text = "hello world";
    std::string pattern = "world";
    if (bruteForceMatch(text, pattern)) {
        std::cout << "Pattern found at index " << (text.find(pattern) - text.size()) << std::endl;
    } else {
        std::cout << "Pattern not found" << std::endl;
    }
    return 0;
}

**2. Knuth-Morris-Pratt (KMP) 算法**
KMP算法通过预处理模式串构建一个失配表，避免了不必要的回溯。当模式串的当前字符与文本串不匹配时，会利用失配表直接跳到适当的下标继续匹配，提高了效率。时间复杂度为O(n + m)，比BF更优。

#include <vector>
#include <string>

std::vector<int> getFailTable(const std::string& pattern) {
    int fail[patSize] = {0};
    for (size_t i = 1; i < pattern.size(); ++i) {
        while (fail[i] > 0 && pattern[fail[i]] != pattern[i]) {
            fail[i] = fail[fail[i]];
        }
        if (pattern[i] == pattern[fail[i]]) {
            fail[i]++;
        }
    }
    return fail;
}

bool kmpMatch(const std::string& text, const std::string& pattern) {
    auto failTable = getFailTable(pattern);
    size_t i = 0, j = 0;
    while (i < text.size() && j < pattern.size()) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        } else if (j > 0) {
            j = fail[j];
        } else {
            i++;
        }
    }
    return j == pattern.size();
}

int main() {
    std::string text = "hello world";
    std::string pattern = "world";
    if (kmpMatch(text, pattern)) {
        std::cout << "Pattern found at index " << (text.find(pattern) - text.size()) << std::endl;
    } else {
        stdcout << "Pattern not found" << std::endl;
    }
    return 0;
}