string/deque_rolling_hash.hpp

• View this file on GitHub
• Last update: 2024-11-29 20:31:18+09:00
• Include: #include "string/deque_rolling_hash.hpp"

Depends on

• mod/modint61.hpp

Code

#include "mod/modint61.hpp"

// 特に pop はテストされてない
template <typename CHAR>
struct Deque_Rolling_Hash {
  using mint = modint61;
  // prefix hash(n) = dat[n]+a*pow[n]
  mint a;
  mint base, ibase;
  vc<mint> pow_table;
  deque<CHAR> S;
  deque<mint> dat;
  Deque_Rolling_Hash() : a(0) { dat.eb(0); }

  void set_base(mint _base, mint _ibase) {
    base = _base, ibase = _ibase;
    assert(base * ibase == 1);
    pow_table = {mint(1), base};
  }
  int size() { return S.size(); }

  CHAR pop_l() {
    dat.pop_front();
    CHAR ch = S.front();
    S.pop_front();
    a = a * base - ch;
    return ch;
  }
  CHAR pop_r() {
    dat.pop_back();
    CHAR ch = S.back();
    S.pop_back();
    return ch;
  }

  void add_l(CHAR ch) {
    assert(len(pow_table) >= 2); // set base?
    S.emplace_front(ch);
    a = (a + ch) * ibase;
    dat.emplace_front(-a);
    assert(get(0, 1) != 0);
  }
  void add_r(CHAR ch) {
    assert(len(pow_table) >= 2); // set base?
    S.eb(ch), dat.eb(dat.back() * base + ch);
    assert(get(0, 1) != 0);
  }

  mint get(int l, int r) {
    assert(0 <= l && l <= r && r <= len(S));
    return dat[r] - dat[l] * pow(r - l);
  }

  mint pow(int i) {
    while (i >= len(pow_table)) pow_table.eb(pow_table.back() * pow_table[1]);
    return pow_table[i];
  }
};

#line 2 "mod/modint61.hpp"

struct modint61 {
  static constexpr u64 mod = (1ULL << 61) - 1;
  u64 val;
  constexpr modint61() : val(0ULL) {}
  constexpr modint61(u32 x) : val(x) {}
  constexpr modint61(u64 x) : val(x % mod) {}
  constexpr modint61(int x) : val((x < 0) ? (x + static_cast<ll>(mod)) : x) {}
  constexpr modint61(ll x) : val(((x %= static_cast<ll>(mod)) < 0) ? (x + static_cast<ll>(mod)) : x) {}
  static constexpr u64 get_mod() { return mod; }

  modint61 &operator+=(const modint61 &a) {
    val = ((val += a.val) >= mod) ? (val - mod) : val;
    return *this;
  }
  modint61 &operator-=(const modint61 &a) {
    val = ((val -= a.val) >= mod) ? (val + mod) : val;
    return *this;
  }
  modint61 &operator*=(const modint61 &a) {
    const unsigned __int128 y = static_cast<unsigned __int128>(val) * a.val;
    val = (y >> 61) + (y & mod);
    val = (val >= mod) ? (val - mod) : val;
    return *this;
  }
  modint61 operator-() const { return modint61(val ? mod - val : u64(0)); }
  modint61 &operator/=(const modint61 &a) { return (*this *= a.inverse()); }
  modint61 operator+(const modint61 &p) const { return modint61(*this) += p; }
  modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; }
  modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; }
  modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; }
  bool operator<(const modint61 &other) const { return val < other.val; }
  bool operator==(const modint61 &p) const { return val == p.val; }
  bool operator!=(const modint61 &p) const { return val != p.val; }
  modint61 inverse() const {
    ll a = val, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b), swap(u -= t * v, v);
    }
    return modint61(u);
  }
  modint61 pow(ll n) const {
    assert(n >= 0);
    modint61 ret(1), mul(val);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul, n >>= 1;
    }
    return ret;
  }
};

#ifdef FASTIO
void rd(modint61 &x) {
  fastio::rd(x.val);
  assert(0 <= x.val && x.val < modint61::mod);
}

void wt(modint61 x) { fastio::wt(x.val); }
#endif
#line 2 "string/deque_rolling_hash.hpp"

// 特に pop はテストされてない
template <typename CHAR>
struct Deque_Rolling_Hash {
  using mint = modint61;
  // prefix hash(n) = dat[n]+a*pow[n]
  mint a;
  mint base, ibase;
  vc<mint> pow_table;
  deque<CHAR> S;
  deque<mint> dat;
  Deque_Rolling_Hash() : a(0) { dat.eb(0); }

  void set_base(mint _base, mint _ibase) {
    base = _base, ibase = _ibase;
    assert(base * ibase == 1);
    pow_table = {mint(1), base};
  }
  int size() { return S.size(); }

  CHAR pop_l() {
    dat.pop_front();
    CHAR ch = S.front();
    S.pop_front();
    a = a * base - ch;
    return ch;
  }
  CHAR pop_r() {
    dat.pop_back();
    CHAR ch = S.back();
    S.pop_back();
    return ch;
  }

  void add_l(CHAR ch) {
    assert(len(pow_table) >= 2); // set base?
    S.emplace_front(ch);
    a = (a + ch) * ibase;
    dat.emplace_front(-a);
    assert(get(0, 1) != 0);
  }
  void add_r(CHAR ch) {
    assert(len(pow_table) >= 2); // set base?
    S.eb(ch), dat.eb(dat.back() * base + ch);
    assert(get(0, 1) != 0);
  }

  mint get(int l, int r) {
    assert(0 <= l && l <= r && r <= len(S));
    return dat[r] - dat[l] * pow(r - l);
  }

  mint pow(int i) {
    while (i >= len(pow_table)) pow_table.eb(pow_table.back() * pow_table[1]);
    return pow_table[i];
  }
};

Back to top page