rolling hash
(include/emthrm/string/rolling_hash.hpp)

• View this file on GitHub
• Last update: 2023-02-04 14:26:45+09:00
• Include: #include "emthrm/string/rolling_hash.hpp"

時間計算量

$\langle O(\lvert S \rvert), O(1) \rangle$

仕様

template <typename T = char>
struct RollingHash;

• T：$S$ の要素型

メンバ変数

名前	説明
std::vector<T> str	$S$

メンバ関数

名前	効果・戻り値	要件
template <typename U> explicit RollingHash(const U& str_, const std::int64_t base = generate_base());	$S$ に対してオブジェクトを構築する。
void add(const T ch);	$S$ の末尾に $\mathrm{ch}$ を追加する。	$0 \leq \mathrm{ch} < 2^{61} - 1$
std::int64_t get(const int left, const int right) const;	S[left:right] におけるハッシュ値

参考文献

• https://www.slideshare.net/nagisaeto/rolling-hash-149990902
• https://togetter.com/li/1413936
• https://twitter.com/noshi91/status/1269257182870073344
• https://twitter.com/noshi91/status/1612080505318707201

TODO

• 2次元 rolling hash
  • https://github.com/beet-aizu/library/blob/42bf89efb7043053ac652a0053cf0a8e325195ca/string/rectanglehash.cpp
  • https://github.com/NyaanNyaan/library/blob/06f3f98a5aada992bfc5e83b6f59363694179635/string/rolling-hash-2d.hpp
  • https://github.com/kopricky/My-Algorithm/blob/4cb6da81e5e904422d0c153e5afe0bd6a25874c6/Competitive_Programming/ICPC/ICPC_rolling_hash_2d.hpp

Submissons

https://atcoder.jp/contests/abc141/submissions/38527267

Verified with

• 文字列/rolling hash (test/string/rolling_hash.test.cpp)

Code

#ifndef EMTHRM_STRING_ROLLING_HASH_HPP_
#define EMTHRM_STRING_ROLLING_HASH_HPP_

#include <cassert>
#include <cstdint>
#include <random>
#include <vector>

namespace emthrm {

template <typename T = char>
struct RollingHash {
  const std::int64_t base;
  std::vector<T> str;

  template <typename U>
  explicit RollingHash(const U& str_, const std::int64_t base = generate_base())
      : base(base), hashes({0}), powers({1}) {
    const int n = str_.size();
    str.reserve(n);
    hashes.reserve(n + 1);
    powers.reserve(n + 1);
    for (const auto ch : str_) add(ch);
  }

  void add(const T ch) {
    assert(0 <= ch && ch < MOD);
    str.emplace_back(ch);
    const std::int64_t h = mul(hashes.back(), base) + ch;
    hashes.emplace_back(h >= MOD ? h - MOD : h);
    const std::int64_t p = mul(powers.back(), base);
    powers.emplace_back(p);
  }

  std::int64_t get(const int left, const int right) const {
    const std::int64_t res =
        hashes[right] - mul(hashes[left], powers[right - left]);
    return res < 0 ? res + MOD : res;
  }

 private:
  static constexpr int MOD_WIDTH = 61;
  static constexpr std::int64_t MOD = (INT64_C(1) << MOD_WIDTH) - 1;

  std::vector<std::int64_t> hashes, powers;

  static std::int64_t generate_base() {
    static std::mt19937_64 engine(std::random_device {} ());
    static std::uniform_int_distribution<std::int64_t> dist(0, MOD - 1);
    return dist(engine);
  }

  static std::int64_t mul(const std::int64_t a, const std::int64_t b) {
    const std::int64_t au = a >> 31, ad = a & ((UINT32_C(1) << 31) - 1);
    const std::int32_t bu = b >> 31, bd = b & ((UINT32_C(1) << 31) - 1);
    const std::int64_t mid = au * bd + ad * bu;
    std::int64_t res = au * bu * 2 + ad * bd + (mid >> 30)
                       + ((mid & ((UINT32_C(1) << 30) - 1)) << 31);
    res = (res >> MOD_WIDTH) + (res & MOD);
    return res >= MOD ? res - MOD : res;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_STRING_ROLLING_HASH_HPP_

#line 1 "include/emthrm/string/rolling_hash.hpp"



#include <cassert>
#include <cstdint>
#include <random>
#include <vector>

namespace emthrm {

template <typename T = char>
struct RollingHash {
  const std::int64_t base;
  std::vector<T> str;

  template <typename U>
  explicit RollingHash(const U& str_, const std::int64_t base = generate_base())
      : base(base), hashes({0}), powers({1}) {
    const int n = str_.size();
    str.reserve(n);
    hashes.reserve(n + 1);
    powers.reserve(n + 1);
    for (const auto ch : str_) add(ch);
  }

  void add(const T ch) {
    assert(0 <= ch && ch < MOD);
    str.emplace_back(ch);
    const std::int64_t h = mul(hashes.back(), base) + ch;
    hashes.emplace_back(h >= MOD ? h - MOD : h);
    const std::int64_t p = mul(powers.back(), base);
    powers.emplace_back(p);
  }

  std::int64_t get(const int left, const int right) const {
    const std::int64_t res =
        hashes[right] - mul(hashes[left], powers[right - left]);
    return res < 0 ? res + MOD : res;
  }

 private:
  static constexpr int MOD_WIDTH = 61;
  static constexpr std::int64_t MOD = (INT64_C(1) << MOD_WIDTH) - 1;

  std::vector<std::int64_t> hashes, powers;

  static std::int64_t generate_base() {
    static std::mt19937_64 engine(std::random_device {} ());
    static std::uniform_int_distribution<std::int64_t> dist(0, MOD - 1);
    return dist(engine);
  }

  static std::int64_t mul(const std::int64_t a, const std::int64_t b) {
    const std::int64_t au = a >> 31, ad = a & ((UINT32_C(1) << 31) - 1);
    const std::int32_t bu = b >> 31, bd = b & ((UINT32_C(1) << 31) - 1);
    const std::int64_t mid = au * bd + ad * bu;
    std::int64_t res = au * bu * 2 + ad * bd + (mid >> 30)
                       + ((mid & ((UINT32_C(1) << 30) - 1)) << 31);
    res = (res >> MOD_WIDTH) + (res & MOD);
    return res >= MOD ? res - MOD : res;
  }
};

}  // namespace emthrm

Back to top page