用bf算法实现模式串匹配的cpp程序

Bloom Filter是一种空间效率很高的概率型数据结构，常用于快速判断一个元素是否在一个集合中，但可能会有误判。在模式串匹配中，BF算法主要用于检测是否存在某个字符串作为子串，而不是精确查找。

以下是使用Bloom Filter实现模式串匹配的一个简单C++程序示例。请注意，Bloom Filter并不适合用于需要精确匹配的情况，因为存在一定的误报率。

#include <vector>
#include <cstdlib>
#include <ctime>

// Bloom Filter的构造函数，设置位数组大小和哈希函数的数量
class BloomFilter {
private:
    std::vector<bool> filter;
    int m, k;

public:
    BloomFilter(int size, int hash_num) : m(size), k(hash_num) {
        filter.resize(m, false);
    }

    // 哈希函数，这里仅做演示，实际应用中需要更复杂的散列策略
    inline uint32_t hash(uint64_t key, int idx) const {
        return static_cast<uint32_t>((key * idx) % m);
    }

    void add(const std::string &str) {
        for (char c : str) {
            for (int i = 0; i < k; ++i) {
                if (!filter[hash(c + i, i)]) {
                    filter[hash(c + i, i)] = true;
                }
            }
        }
    }

    bool contains(const std::string &str) {
        for (char c : str) {
            bool exists = true;
            for (int i = 0; i < k; ++i) {
                if (!filter[hash(c + i, i)]) {
                    exists = false;
                    break;
                }
            }
            if (!exists) return false;
        }
        return true;
    }
};

int main() {
    srand(time(0)); // 初始化随机数生成器
    BloomFilter bf(100000, 5); // 创建一个大小为100000的Bloom Filter，使用5个哈希函数
    std::string pattern = "test pattern"; // 待检查的模式串
    bf.add(pattern); // 添加模式到过滤器

    std::string text = "This is a test string with the pattern repeated.";
    if (bf.contains(text)) {
        std::cout << "疑似找到匹配模式！" << std::endl;
    } else {
        std::cout << "未找到匹配模式，可能存在误报。" << std::endl;
    }
    
    return 0;
}