c++20 实现bm搜索

C++20 中没有原生的 BM 算法实现，但可以通过自己编写实现。以下是一种基于 C++20 的 BM 算法实现：

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<int> get_bad_table(const std::string& pattern) {
    std::vector<int> bad_table(256, pattern.size());
    for (int i = 0; i < pattern.size() - 1; ++i) {
        bad_table[pattern[i]] = pattern.size() - i - 1;
    }
    return bad_table;
}

std::vector<int> get_good_table(const std::string& pattern) {
    std::vector<int> good_table(pattern.size(), pattern.size());
    int last_prefix_pos = pattern.size();
    for (int i = pattern.size() - 1; i >= 0; --i) {
        if (pattern[i] == pattern[pattern.size() - 1 - (last_prefix_pos - i)]) {
            good_table[i] = last_prefix_pos - i - 1;
        } else {
            last_prefix_pos = i;
        }
    }
    for (int i = 0; i < pattern.size() - 1; ++i) {
        int suffix_len = 0;
        while (pattern[i - suffix_len] == pattern[pattern.size() - 1 - suffix_len] && suffix_len < i) {
            ++suffix_len;
        }
        good_table[pattern.size() - 1 - suffix_len] = i - suffix_len;
    }
    return good_table;
}

std::vector<int> bm_search(const std::string& text, const std::string& pattern) {
    std::vector<int> bad_table = get_bad_table(pattern);
    std::vector<int> good_table = get_good_table(pattern);
    std::vector<int> result;
    int i = pattern.size() - 1;
    while (i < text.size()) {
        int j = pattern.size() - 1;
        while (j >= 0 && text[i] == pattern[j]) {
            --i;
            --j;
        }
        if (j < 0) {
            result.push_back(i + 1);
            i += pattern.size() * 2 - 1;
        } else {
            int bad_shift = bad_table[text[i]] - pattern.size() + j + 1;
            int good_shift = good_table[j];
            i += std::max(bad_shift, good_shift);
        }
    }
    return result;
}

int main() {
    std::string text = "ABAAAABCAC";
    std::string pattern = "ABC";
    std::vector<int> result = bm_search(text, pattern);
    for (int pos : result) {
        std::cout << pos << " ";
    }
    std::cout << std::endl;
    return 0;
}

该实现中，get_bad_table 函数生成了坏字符表，get_good_table 函数生成了好后缀表，bm_search 函数使用坏字符表和好后缀表进行匹配。在匹配过程中，如果发现不匹配，则根据坏字符表和好后缀表计算出需要移动的距离，然后移动到下一个可能匹配的位置。

该实现的时间复杂度为 O(n/m)，其中 n 为文本串的长度，m 为模式串的长度。空间复杂度为 O(m)。