Rolling-Hash(ローリングハッシュ) (string/rolling-hash.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "string/rolling-hash.hpp"
• Link: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6

概要

文字列の一致判定を mod $2^{61}-1$ のハッシュを用いて効率的に行う.

• RollingHash(base): 基数 base のローリングハッシュを構築する.
• generate_base(): $2^{61} - 1$ 以下の乱数を返す。これを base とすると Hack されにくい.
• build(s): 文字列 s のハッシュテーブルを返す.
• query(s, l, r): s の区間 $[l, r)$ のハッシュ値を返す.
• combine(h1, h2, h2len): ハッシュ値 h1 と長さ h2len のハッシュ値 h2 を結合する. power[h2len] での配列外参照に注意(TODO 実装).
• lcp(a, l1, r1, b, l2, r2): ハッシュテーブル a の区間 $[l1, r1)$ と, ハッシュテーブル b の区間 $[l2, r2)$ の文字列の最長共通接頭辞の長さを返す.

計算量

• build(): $O(n)$
• lcp(): $O(\log n)$
• クエリ: $O(1)$

Verified with

• test/verify/aoj-alds-1-14-b.test.cpp

Code

/**
 * @brief Rolling-Hash(ローリングハッシュ)
 * @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
 *
 */
struct RollingHash {
  static const uint64_t mod = (1ull << 61ull) - 1;
  using uint128_t = __uint128_t;
  vector<uint64_t> power;
  const uint64_t base;

  static inline uint64_t add(uint64_t a, uint64_t b) {
    if ((a += b) >= mod) a -= mod;
    return a;
  }

  static inline uint64_t mul(uint64_t a, uint64_t b) {
    uint128_t c = (uint128_t)a * b;
    return add(c >> 61, c & mod);
  }

  static inline uint64_t generate_base() {
    mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<uint64_t> rand(1, RollingHash::mod - 1);
    return rand(mt);
  }

  inline void expand(size_t sz) {
    if (power.size() < sz + 1) {
      int pre_sz = (int)power.size();
      power.resize(sz + 1);
      for (int i = pre_sz - 1; i < sz; i++) {
        power[i + 1] = mul(power[i], base);
      }
    }
  }

  explicit RollingHash(uint64_t base = generate_base())
      : base(base), power{1} {}

  vector<uint64_t> build(const string &s) const {
    int sz = s.size();
    vector<uint64_t> hashed(sz + 1);
    for (int i = 0; i < sz; i++) {
      hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
  }

  template <typename T>
  vector<uint64_t> build(const vector<T> &s) const {
    int sz = s.size();
    vector<uint64_t> hashed(sz + 1);
    for (int i = 0; i < sz; i++) {
      hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
  }

  uint64_t query(const vector<uint64_t> &s, int l, int r) {
    expand(r - l);
    return add(s[r], mod - mul(s[l], power[r - l]));
  }

  uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) {
    expand(h2len);
    return add(mul(h1, power[h2len]), h2);
  }

  int lcp(const vector<uint64_t> &a, int l1, int r1, const vector<uint64_t> &b,
          int l2, int r2) {
    int len = min(r1 - l1, r2 - l2);
    int low = 0, high = len + 1;
    while (high - low > 1) {
      int mid = (low + high) / 2;
      if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid))
        low = mid;
      else
        high = mid;
    }
    return low;
  }
};

#line 1 "string/rolling-hash.hpp"
/**
 * @brief Rolling-Hash(ローリングハッシュ)
 * @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
 *
 */
struct RollingHash {
  static const uint64_t mod = (1ull << 61ull) - 1;
  using uint128_t = __uint128_t;
  vector<uint64_t> power;
  const uint64_t base;

  static inline uint64_t add(uint64_t a, uint64_t b) {
    if ((a += b) >= mod) a -= mod;
    return a;
  }

  static inline uint64_t mul(uint64_t a, uint64_t b) {
    uint128_t c = (uint128_t)a * b;
    return add(c >> 61, c & mod);
  }

  static inline uint64_t generate_base() {
    mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<uint64_t> rand(1, RollingHash::mod - 1);
    return rand(mt);
  }

  inline void expand(size_t sz) {
    if (power.size() < sz + 1) {
      int pre_sz = (int)power.size();
      power.resize(sz + 1);
      for (int i = pre_sz - 1; i < sz; i++) {
        power[i + 1] = mul(power[i], base);
      }
    }
  }

  explicit RollingHash(uint64_t base = generate_base())
      : base(base), power{1} {}

  vector<uint64_t> build(const string &s) const {
    int sz = s.size();
    vector<uint64_t> hashed(sz + 1);
    for (int i = 0; i < sz; i++) {
      hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
  }

  template <typename T>
  vector<uint64_t> build(const vector<T> &s) const {
    int sz = s.size();
    vector<uint64_t> hashed(sz + 1);
    for (int i = 0; i < sz; i++) {
      hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
  }

  uint64_t query(const vector<uint64_t> &s, int l, int r) {
    expand(r - l);
    return add(s[r], mod - mul(s[l], power[r - l]));
  }

  uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) {
    expand(h2len);
    return add(mul(h1, power[h2len]), h2);
  }

  int lcp(const vector<uint64_t> &a, int l1, int r1, const vector<uint64_t> &b,
          int l2, int r2) {
    int len = min(r1 - l1, r2 - l2);
    int low = 0, high = len + 1;
    while (high - low > 1) {
      int mid = (low + high) / 2;
      if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid))
        low = mid;
      else
        high = mid;
    }
    return low;
  }
};

Back to top page