:heavy_check_mark: string/rolling-hash-monoid.hpp

Depends on

Required by

Verified with

Code

#pragma once

#include "string/rolling-hash-value.hpp"

struct RollingHashMonoid {
  using value_type = RollingHashValue;
  static value_type op(value_type x, value_type y) { return x + y; }
  static value_type e() { return value_type(); }
  template <class T>
  static value_type single(T v) {
    return value_type::single(v);
  }
  template <class Sequence>
  static vector<value_type> init(const Sequence& a) {
    vector<value_type> v(a.size());
    for (int i = 0; i < (int)a.size(); i++) v[i] = single(a[i]);
    return v;
  }
};

struct RollingHashMonoidReversible {
  using value_type = RollingHashValueReversible;
  static value_type op(value_type x, value_type y) { return x + y; }
  static value_type e() { return value_type(); }
  template <class T>
  static value_type single(T v) {
    return value_type::single(v);
  }
  template <class Sequence>
  static vector<value_type> init(const Sequence& a) {
    vector<value_type> v(a.size());
    for (int i = 0; i < (int)a.size(); i++) v[i] = single(a[i]);
    return v;
  }
};
#line 2 "string/rolling-hash-monoid.hpp"

#line 2 "string/rolling-hash-value.hpp"

#line 2 "string/rolling-hash-base.hpp"

struct RollingHashBase {
  using u128 = __uint128_t;
  using i128 = __int128_t;
  using u64 = uint64_t;
  static constexpr u64 MOD = (1ull << 61) - 1;
  static u64 base;
  static u64 add(u64 x, u64 y) {
    if ((x += y) >= MOD) x -= MOD;
    return x;
  }
  static u64 sub(u64 x, u64 y) {
    if ((x -= y) >= MOD) x += MOD;
    return x;
  }
  static u64 mul(u64 x, u64 y) {
    u128 z = (u128)x * y;
    u64 v = (u64(z) & MOD) + u64(z >> 61);
    return v >= MOD ? v - MOD : v;
  }
  static u64 normalize(u64 v) {
    u64 x = (v & MOD) + (v >> 61);
    return x >= MOD ? x - MOD : x;
  }
  template <class T>
  static u64 normalize(T v) {
    static_assert(is_integral_v<T> && sizeof(T) <= sizeof(u64));
    if constexpr (is_signed_v<T>) {
      if (v < 0) {
        u64 x = normalize(u64(-i128(v)));
        return x == 0 ? 0 : MOD - x;
      }
    }
    return normalize(u64(v));
  }
  template <class T>
  static T restore(u64 v) {
    static_assert(is_integral_v<T> && sizeof(T) <= sizeof(u64));
    assert(v < MOD);
    if constexpr (is_signed_v<T>) {
      if (v <= u64(numeric_limits<T>::max())) return T(v);
      u64 x = MOD - v;
      assert(i128(x) <= -i128(numeric_limits<T>::min()));
      return T(-i128(x));
    } else {
      assert(v <= u64(numeric_limits<T>::max()));
      return T(v);
    }
  }
};
inline RollingHashBase::u64 RollingHashBase::base = []() {
  random_device seed_gen;
  mt19937_64 rnd(seed_gen());
  return uniform_int_distribution<u64>(256, MOD - 2)(rnd);
}();
#line 4 "string/rolling-hash-value.hpp"

struct RollingHashValue : RollingHashBase {
  u64 hash, power;
  RollingHashValue() : hash(0), power(1) {}
  RollingHashValue(u64 h, u64 p) : hash(h), power(p) {}
  template <class T>
  static RollingHashValue single(T v) {
    return RollingHashValue(normalize(v), base);
  }
  RollingHashValue& operator+=(RollingHashValue rhs) {
    hash = add(mul(hash, rhs.power), rhs.hash);
    power = mul(power, rhs.power);
    return *this;
  }
  friend RollingHashValue operator+(RollingHashValue lhs, RollingHashValue rhs) {
    return lhs += rhs;
  }
  friend bool operator==(RollingHashValue lhs, RollingHashValue rhs) {
    return lhs.hash == rhs.hash && lhs.power == rhs.power;
  }
};

struct RollingHashValueReversible : RollingHashBase {
  u64 hash, reverse_hash, power;
  RollingHashValueReversible() : hash(0), reverse_hash(0), power(1) {}
  RollingHashValueReversible(u64 h, u64 rh, u64 p) : hash(h), reverse_hash(rh), power(p) {}
  template <class T>
  static RollingHashValueReversible single(T v) {
    u64 h = normalize(v);
    return RollingHashValueReversible(h, h, base);
  }
  RollingHashValueReversible& operator+=(RollingHashValueReversible rhs) {
    hash = add(mul(hash, rhs.power), rhs.hash);
    reverse_hash = add(reverse_hash, mul(rhs.reverse_hash, power));
    power = mul(power, rhs.power);
    return *this;
  }
  RollingHashValueReversible reversed() const {
    return RollingHashValueReversible(reverse_hash, hash, power);
  }
  friend RollingHashValueReversible operator+(RollingHashValueReversible lhs,
                                              RollingHashValueReversible rhs) {
    return lhs += rhs;
  }
  friend bool operator==(RollingHashValueReversible lhs, RollingHashValueReversible rhs) {
    return lhs.hash == rhs.hash && lhs.reverse_hash == rhs.reverse_hash &&
           lhs.power == rhs.power;
  }
};
#line 4 "string/rolling-hash-monoid.hpp"

struct RollingHashMonoid {
  using value_type = RollingHashValue;
  static value_type op(value_type x, value_type y) { return x + y; }
  static value_type e() { return value_type(); }
  template <class T>
  static value_type single(T v) {
    return value_type::single(v);
  }
  template <class Sequence>
  static vector<value_type> init(const Sequence& a) {
    vector<value_type> v(a.size());
    for (int i = 0; i < (int)a.size(); i++) v[i] = single(a[i]);
    return v;
  }
};

struct RollingHashMonoidReversible {
  using value_type = RollingHashValueReversible;
  static value_type op(value_type x, value_type y) { return x + y; }
  static value_type e() { return value_type(); }
  template <class T>
  static value_type single(T v) {
    return value_type::single(v);
  }
  template <class Sequence>
  static vector<value_type> init(const Sequence& a) {
    vector<value_type> v(a.size());
    for (int i = 0; i < (int)a.size(); i++) v[i] = single(a[i]);
    return v;
  }
};
Back to top page