C++字符串应用算法：用BF和KMP算法实现两个字符串的模式匹配

C++ 字符串的模式匹配通常涉及到寻找一个主字符串（text string）中是否存在另一个给定的模式串（pattern）。其中，Brute Force (BF) 算法简单粗暴，而 Knuth-Morris-Pratt (KMP) 算法则更为高效。

**1. Brute Force (BF) 算法**：
这个是最直接的方法，遍历主字符串中的每个字符，逐个与模式串对比。如果遇到不匹配的字符，就从当前位置开始继续搜索，直到找到匹配或者搜索完整个主字符串。这种做法的时间复杂度是 O(nm)，其中 n 是主字符串长度，m 是模式串长度。

bool bf_match(string text, string pattern) {
    for (size_t i = 0; i <= text.size() - pattern.size(); ++i) {
        bool match = true;
        for (size_t j = 0; j < pattern.size(); ++j) {
            if (text[i + j] != pattern[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

**2. Knuth-Morris-Pratt (KMP) 算法**：
KMP 算法通过预处理模式串构建一个失配表（also called failure function），使得在不匹配时能快速跳过部分已匹配过的字符，避免了大量无谓的回溯。时间复杂度可以降低到 O(n+m)，比 BF 更快。

void build_table(string pattern, vector<int>& table) {
    int index = 0;
    for (int i = 1; i < pattern.size(); ++i) {
        while (index > 0 && pattern[index] != pattern[i]) index = table[index - 1];
        if (pattern[index] == pattern[i]) ++index;
        table.push_back(index);
    }
}

bool kmp_match(string text, string pattern) {
    vector<int> table(pattern.size());
    build_table(pattern, table);
    size_t i = 0, j = 0;
    while (i < text.size()) {
        if (text[i] == pattern[j]) {
            ++i;
            ++j;
        } else if (j > 0) {
            j = table[j - 1];
        } else {
            ++i;
        }
        if (j == pattern.size()) return true;
    }
    return false;
}