BloomFilter.cpp

#include <bits/stdc++.h>
typedef long long ll;
typedef std::tuple<ll, ll, ll> hash_t;
using namespace std;

class RollingHash {
  public:
    hash_t p = {13, 31, 19};
    hash_t hashes = {0, 0, 0};
    hash_t pows = {1, 1, 1};
    hash_t mods = {1200000041LL, 1400000023LL, 1000000009LL};
    void add(ll x) {
      get<0>(pows) = (get<0>(pows) * get<0>(p)) % get<0>(mods);
      get<0>(hashes) = ((get<0>(hashes) + x) * get<0>(p)) % get<0>(mods);
      get<1>(pows) = (get<1>(pows) * get<1>(p)) % get<1>(mods);
      get<1>(hashes) = ((get<1>(hashes) + x) * get<1>(p)) % get<1>(mods);
      get<2>(pows) = (get<2>(pows) * get<2>(p)) % get<2>(mods);
      get<2>(hashes) = ((get<2>(hashes) + x) * get<2>(p)) % get<2>(mods);
    }
    void step(ll oldChar, ll newChar) {
      get<0>(hashes) = (get<0>(hashes) - oldChar * get<0>(pows) + 10000*get<0>(mods)) % get<0>(mods);
      get<1>(hashes) = (get<1>(hashes) - oldChar * get<1>(pows) + 10000*get<1>(mods)) % get<1>(mods);
      get<2>(hashes) = (get<2>(hashes) - oldChar * get<2>(pows) + 10000*get<2>(mods)) % get<2>(mods);
      get<0>(hashes) = ((get<0>(hashes) + newChar) * get<0>(p)) % get<0>(mods);
      get<1>(hashes) = ((get<1>(hashes) + newChar) * get<1>(p)) % get<1>(mods);
      get<2>(hashes) = ((get<2>(hashes) + newChar) * get<2>(p)) % get<2>(mods);
    }
    auto getHash() { return hashes; }
};