题解 | #redis布隆过滤器#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s1 string字符串vector
     * @param s2 string字符串vector
     * @param n int整型
     * @return int整型vector
     */
    set<string> st;
    vector<int> v;
    int k = 0;
    void init(int n) {
        k = n;
        for (int i = 0; i < n; i++) {
            v.push_back(10000 + rand() % 10001);
        }
    }
    void add(string s) {
        int key = 0;
        string str;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < s.length(); j++) {
                key = (i * key + (int)s[j]) % v[i - 1];
            }
            str += to_string(key);
            str += ",";
            key = 0;
        }
        st.insert(str);
    }
    bool contains(string s) {
        int key = 0;
        string str;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < s.length(); j++) {
                key = (i * key + (int)s[j]) % v[i - 1];
            }
            str += to_string(key);
            str += ",";
            key = 0;
        }
        if (st.find(str) != st.end()) {
            return true;
        } else {
            return false;
        }
    }
    vector<int> BloomFilter(vector<string>& s1, vector<string>& s2, int n) {
        // write code here
        init(n);
        vector<int> v;
        for (string s : s1) {
            add(s);
        }
        for (string s : s2) {
            if (contains(s)) {
                v.push_back(1);
            } else {
                v.push_back(0);
            }
        }
        return v;
    }
};