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

• View this file on GitHub
• Last update: 2025-04-29 18:43:20+09:00
• Include: #include "string/rolling-hash.hpp"

RollingHashを扱う。

文字列Sのハッシュは、$ \Sum_{i=0, 1, \dots

S

} b^i S[i] $とする。

Hash

文字列のハッシュを表現する。 文字列の長さ、基数、ハッシュの値を持つ。

コンストラクタ

Hash(mint _hash, mint _base, int _len)

ハッシュした値が_hashで、基数が_baseであり、その文字列は_lenの長さであるとしてハッシュを初期化する。

operator+(const Hash& rhs) const

rhsを文字列として右から結合したあとのHashを返す。 基数が同じであることを要求する。

RollingHash

文字列のHashを扱う。先頭からのハッシュを管理しておくことで、部分文字列のハッシュ計算なども対応する。

コンストラクタ

RollingHash(const string& S, mint _base): (_base)

get

Hash get(int l, int r) const

$S$の$[l,r)$部分のハッシュを計算する。 $mod$は定数なので計算量は$O(1)$

Depends on

• math/modint2611.hpp

Verified with

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

Code

#ifndef HARUILIB_LIBRARY_STRING_ROLLING_HASH_HPP
#define HARUILIB_LIBRARY_STRING_ROLLING_HASH_HPP

#include <iostream>
#include <vector>
#include <string>

#include "math/modint2611.hpp"

struct Hash {
  using mint = modint2611;
  mint hash;
  mint base;
  int len;

  // コンストラクタ
  constexpr Hash(mint _hash, mint _base, int _len): hash(_hash), base(_base), len(_len) {
  }

  // 文字列sのハッシュを返す
  constexpr Hash(std::string s, mint _base): hash(mint(0)), base(_base) {
    hash = mint(0);
    base = _base;
    len = int(s.size());

    mint pow = mint(1);
    for (int i=0; i<int(s.size()); i++){
      hash += pow * mint(s[i]);
      pow *= base;
    }
  }

  // 文字cのハッシュを返す
  constexpr Hash(char c, mint _base): base(_base) {
    hash = mint(c) * base;
    len = 1;
  }

  // 文字列としての結合をしたあとのHashを返す
  constexpr Hash& operator+=(const Hash& rhs) {
    assert(base == rhs.base);
    hash += base.pow(len) * rhs.hash;
    len += rhs.len;
    return *this;
  }

  // 文字列としての結合をしたあとのHashを返す
  constexpr Hash& operator+=(const char& c) {
    hash += base.pow(len) * mint(c);
    len++;
    return *this;
  }

  constexpr Hash operator+(const Hash& rhs) const {
    return Hash(*this) += rhs; 
  }

  constexpr Hash operator+(const char& c) const {
    return Hash(*this) + c;
  }

  constexpr bool operator==(const Hash& rhs) const {
    return len == rhs.len && hash == rhs.hash;
  }

  bool operator<(const Hash& rhs) const {
    assert(base == rhs.base);
    if (hash.val() < rhs.hash.val()) return true;
    if (hash.val() > rhs.hash.val()) return false;
    return len < rhs.len;
  }

  bool operator>(const Hash& rhs) const {
    assert(base == rhs.base);
    if (hash.val() > rhs.hash.val()) return false;
    if (hash.val() < rhs.hash.val()) return true;
    return len > rhs.len;
  }

  friend std::ostream& operator<<(std::ostream& os, const Hash& hash) {
    os << "Hash{len: ";
    os << hash.len;
    os << ", hash: ";
    os << hash.hash.val();
    os << ", base: ";
    os << hash.base.val();
    os << "}";
    return os;
  }
};

struct RollingHash {
  using mint = modint2611;
  std::vector<mint> hashes;
  mint base;
  constexpr RollingHash (const std::string& S, mint _base) : base(_base) {
    int N = int(S.size());
    hashes.resize(N+1);
    mint powb = base;
    for (int i=0; i<N; i++) {
      hashes[i+1] = hashes[i] + powb * mint(S[i]);
      powb *= base;
    }
  }

  constexpr Hash get(int l, int r) const {
    assert(0 <= l && l <= r && r < int(hashes.size()));
    mint hash_val = (hashes[r] - hashes[l])*(base.pow(l).inv());
    return Hash(hash_val, base, r-l);
  }

};


#endif // HARUILIB_LIBRARY_STRING_ROLLING_HASH_HPP

#line 1 "string/rolling-hash.hpp"



#include <iostream>
#include <vector>
#include <string>

#line 1 "math/modint2611.hpp"



#include <random>
#include <chrono>
/*
法が2^61 - 1のmodint
cf: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
 */

struct modint2611 {

  constexpr static const uint64_t mod = (1ull << 61ull) - 1;
  using uint128_t = __uint128_t;
  uint64_t _val;

  constexpr explicit modint2611() : _val(0) {}

  constexpr explicit modint2611(uint64_t v) : _val(v) {
    if (_val >= mod) _val -= mod;
  }

  constexpr modint2611& operator+=(const modint2611& rhs) {
    if ((_val += rhs._val) >= mod) _val -= mod;
    return *this;
  }

  constexpr modint2611& operator-=(const modint2611& rhs) {
    if (_val < rhs._val) {
      _val += (mod - rhs._val);
    }
    else {
      _val += -rhs._val;
    }
    return *this;
  }

  constexpr modint2611& operator*=(const modint2611& rhs) {
    uint128_t c = (uint128_t) _val * rhs._val;
    // return (c>>61) + (c & mod);
    uint64_t d = (c>>61) + (c & mod);
    if (d >= mod) d -= mod;

    _val = d;
    return *this;
  }
  
  constexpr modint2611 operator-() const { return modint2611(0) - *this; }

  constexpr modint2611 operator+(const modint2611& a) const {
    return modint2611(*this) += a;
  }

  constexpr modint2611 operator-(const modint2611& a) const {
    return modint2611(*this) -= a;
  }

  constexpr modint2611 operator*(const modint2611& a) const {
    return modint2611(*this) *= a;
  }
  
  constexpr bool operator==(const modint2611& a) const { return _val == a._val; }

  constexpr bool operator!=(const modint2611& a) const { return _val != a._val; }

  constexpr uint64_t val() const {
    return _val;
  }

  constexpr modint2611 pow(uint64_t n) const {
    modint2611 ret = modint2611(1);
    modint2611 base = *this;
    while (n) {
      if (n & 1) ret *= base;
      base *= base;
      n >>= 1;
    }
    return ret;
  }

  constexpr modint2611 inv() const {
    return (*this).pow(mod - 2);
  }

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

    return modint2611(rand(mt));
  }

};


#line 9 "string/rolling-hash.hpp"

struct Hash {
  using mint = modint2611;
  mint hash;
  mint base;
  int len;

  // コンストラクタ
  constexpr Hash(mint _hash, mint _base, int _len): hash(_hash), base(_base), len(_len) {
  }

  // 文字列sのハッシュを返す
  constexpr Hash(std::string s, mint _base): hash(mint(0)), base(_base) {
    hash = mint(0);
    base = _base;
    len = int(s.size());

    mint pow = mint(1);
    for (int i=0; i<int(s.size()); i++){
      hash += pow * mint(s[i]);
      pow *= base;
    }
  }

  // 文字cのハッシュを返す
  constexpr Hash(char c, mint _base): base(_base) {
    hash = mint(c) * base;
    len = 1;
  }

  // 文字列としての結合をしたあとのHashを返す
  constexpr Hash& operator+=(const Hash& rhs) {
    assert(base == rhs.base);
    hash += base.pow(len) * rhs.hash;
    len += rhs.len;
    return *this;
  }

  // 文字列としての結合をしたあとのHashを返す
  constexpr Hash& operator+=(const char& c) {
    hash += base.pow(len) * mint(c);
    len++;
    return *this;
  }

  constexpr Hash operator+(const Hash& rhs) const {
    return Hash(*this) += rhs; 
  }

  constexpr Hash operator+(const char& c) const {
    return Hash(*this) + c;
  }

  constexpr bool operator==(const Hash& rhs) const {
    return len == rhs.len && hash == rhs.hash;
  }

  bool operator<(const Hash& rhs) const {
    assert(base == rhs.base);
    if (hash.val() < rhs.hash.val()) return true;
    if (hash.val() > rhs.hash.val()) return false;
    return len < rhs.len;
  }

  bool operator>(const Hash& rhs) const {
    assert(base == rhs.base);
    if (hash.val() > rhs.hash.val()) return false;
    if (hash.val() < rhs.hash.val()) return true;
    return len > rhs.len;
  }

  friend std::ostream& operator<<(std::ostream& os, const Hash& hash) {
    os << "Hash{len: ";
    os << hash.len;
    os << ", hash: ";
    os << hash.hash.val();
    os << ", base: ";
    os << hash.base.val();
    os << "}";
    return os;
  }
};

struct RollingHash {
  using mint = modint2611;
  std::vector<mint> hashes;
  mint base;
  constexpr RollingHash (const std::string& S, mint _base) : base(_base) {
    int N = int(S.size());
    hashes.resize(N+1);
    mint powb = base;
    for (int i=0; i<N; i++) {
      hashes[i+1] = hashes[i] + powb * mint(S[i]);
      powb *= base;
    }
  }

  constexpr Hash get(int l, int r) const {
    assert(0 <= l && l <= r && r < int(hashes.size()));
    mint hash_val = (hashes[r] - hashes[l])*(base.pow(l).inv());
    return Hash(hash_val, base, r-l);
  }

};

Back to top page