高速なローリングハッシュ (Fast Rolling Hash with $\mod 2^{61} - 1$)
(src/sequence/fast-rolling-hash.hpp)

View this file on GitHub
Last update: 2023-08-12 04:06:58+09:00
Include: #include "src/sequence/fast-rolling-hash.hpp"

FastRollingHash

ハッシュの列を扱ういくつかの関数を提供するクラス。

あらかじめ実体化しておき、列の生成や操作はその実体を通して行う必要がある。

(1) FastRollingHash froll;
(2) FastRollingHash froll(u64 b);

(1) froll として実体化する。base は実行時にランダムな原始根がとられる。
(2) base を b と指定し、 froll として実体化する。

以下、実体の変数名を froll であるとする。

Hs

using Hs = std::vector< u64 >;

ハッシュの列の型。 std::vector< u64 > のエイリアスとなっている。

build

template< class Iter >
Hs froll.build(Iter first, Iter last)

Iterator first と last を渡すことで、 $[first, last)$ のハッシュ列を生成する。

計算量

要素数を $n$ として $O(n)$

query

u64 froll.query(const Hs &s, usize l, usize r)

ハッシュ列とその区間 $[l, r)$ を指定し、与えられた区間の hash を計算して返す。

計算量

$O(1)$

combine

u64 froll.combine(u64 h1, u64 h2, usize h2len)

2 つのハッシュ $h1, h2$ と $h2$ の長さ h2len を渡すことで、もとの 2 つの列を連結した列のハッシュを返す。

計算量

$O(1)$

lcp

usize froll.lcp(const Hs &a, usize l1, usize r1,
                const Hs &b, usize l2, usize r2)

列 $A$ のハッシュ列 a とその区間 $[l1, r1)$、列 $B$ のハッシュ列 b とその区間 $[l2, r2)$ を渡すことで、列 $A$ の区間 $[l1, r1)$ と列 $B$ の区間 $[l2, r2)$ の最長共通接頭辞 (Longest Common Prefix) の長さを返す。

計算量

2 つの区間の長さの最小値を $n$ として $O(\log n)$

Depends on

Verified with

Code

#pragma once

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"

#include <algorithm>
#include <cassert>
#include <chrono>
#include <random>
#include <vector>

namespace luz {

  class FastRollingHash {
    static constexpr u64 mod = (1ull << 61ull) - 1;

    const u64 base;
    std::vector< u64 > power;

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

    static u64 mul(u64 a, u64 b) {
      u128 c = u128(a) * b;
      return add(c >> 61, c & mod);
    }

    void expand(usize sz) {
      usize l = power.size(), r = sz + 1;
      if (r <= l) return;

      power.resize(r);
      for (usize i: rep(l, r)) {
        power[i] = mul(power[i - 1], base);
      }
    }

   public:
    using Hs = std::vector< u64 >;

    FastRollingHash(): base(generate_base()), power{1} {}

    explicit FastRollingHash(u64 base): base(base), power{1} {}

    template < class Iter >
    Hs build(Iter first, Iter last) const {
      Hs hs(1);
      hs.reserve(last - first + 1);
      while (first != last) {
        u64 h = add(mul(hs.back(), base), *first);
        hs.emplace_back(h);
        ++first;
      }
      return hs;
    }

    u64 query(const Hs &s, usize l, usize r) {
      assert(l <= r and r < s.size());

      expand(r - l);
      return add(s[r], mod - mul(s[l], power[r - l]));
    }

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

    usize lcp(const Hs &a, usize l1, usize r1, const Hs &b, usize l2,
              usize r2) {
      assert(l1 <= r1 and r1 < a.size());
      assert(l2 <= r2 and r2 < b.size());

      usize len = std::min(r1 - l1, r2 - l2);
      usize low = 0, high = len + 1;

      while (high - low > 1) {
        usize mid = (low + high) / 2;
        if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) {
          low = mid;
        } else {
          high = mid;
        }
      }
      return low;
    }

   private:
    static u64 mod_pow(u64 b, u64 e) {
      u64 res{1};

      while (e) {
        if (e & 1) {
          res = mul(res, b);
        }
        b = mul(b, b);
        e >>= 1;
      }

      return res;
    }

    static bool is_primitive_root(u64 b) {
      constexpr u64 ps[] = {2,  3,  5,  7,   11,  13,
                            31, 41, 61, 151, 331, 1321};
      for (const auto &p: ps) {
        if (mod_pow(b, (mod - 1) / p) == 1) {
          return false;
        }
      }
      return true;
    }

    static u64 generate_base() {
      std::mt19937_64 mt(std::chrono::steady_clock::now()
                             .time_since_epoch()
                             .count());
      std::uniform_int_distribution< u64 > rand(1e9, mod - 1);
      while (true) {
        u64 b = rand(mt);
        if (not is_primitive_root(b)) {
          continue;
        }

        return b;
      }
    }
  };

} // namespace luz

#line 2 "src/sequence/fast-rolling-hash.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 6 "src/sequence/fast-rolling-hash.hpp"

#line 8 "src/sequence/fast-rolling-hash.hpp"
#include <cassert>
#include <chrono>
#include <random>
#include <vector>

namespace luz {

  class FastRollingHash {
    static constexpr u64 mod = (1ull << 61ull) - 1;

    const u64 base;
    std::vector< u64 > power;

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

    static u64 mul(u64 a, u64 b) {
      u128 c = u128(a) * b;
      return add(c >> 61, c & mod);
    }

    void expand(usize sz) {
      usize l = power.size(), r = sz + 1;
      if (r <= l) return;

      power.resize(r);
      for (usize i: rep(l, r)) {
        power[i] = mul(power[i - 1], base);
      }
    }

   public:
    using Hs = std::vector< u64 >;

    FastRollingHash(): base(generate_base()), power{1} {}

    explicit FastRollingHash(u64 base): base(base), power{1} {}

    template < class Iter >
    Hs build(Iter first, Iter last) const {
      Hs hs(1);
      hs.reserve(last - first + 1);
      while (first != last) {
        u64 h = add(mul(hs.back(), base), *first);
        hs.emplace_back(h);
        ++first;
      }
      return hs;
    }

    u64 query(const Hs &s, usize l, usize r) {
      assert(l <= r and r < s.size());

      expand(r - l);
      return add(s[r], mod - mul(s[l], power[r - l]));
    }

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

    usize lcp(const Hs &a, usize l1, usize r1, const Hs &b, usize l2,
              usize r2) {
      assert(l1 <= r1 and r1 < a.size());
      assert(l2 <= r2 and r2 < b.size());

      usize len = std::min(r1 - l1, r2 - l2);
      usize low = 0, high = len + 1;

      while (high - low > 1) {
        usize mid = (low + high) / 2;
        if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) {
          low = mid;
        } else {
          high = mid;
        }
      }
      return low;
    }

   private:
    static u64 mod_pow(u64 b, u64 e) {
      u64 res{1};

      while (e) {
        if (e & 1) {
          res = mul(res, b);
        }
        b = mul(b, b);
        e >>= 1;
      }

      return res;
    }

    static bool is_primitive_root(u64 b) {
      constexpr u64 ps[] = {2,  3,  5,  7,   11,  13,
                            31, 41, 61, 151, 331, 1321};
      for (const auto &p: ps) {
        if (mod_pow(b, (mod - 1) / p) == 1) {
          return false;
        }
      }
      return true;
    }

    static u64 generate_base() {
      std::mt19937_64 mt(std::chrono::steady_clock::now()
                             .time_since_epoch()
                             .count());
      std::uniform_int_distribution< u64 > rand(1e9, mod - 1);
      while (true) {
        u64 b = rand(mt);
        if (not is_primitive_root(b)) {
          continue;
        }

        return b;
      }
    }
  };

} // namespace luz

高速なローリングハッシュ (Fast Rolling Hash with $\mod 2^{61} - 1$) (src/sequence/fast-rolling-hash.hpp)