ローリングハッシュ
(algebra/monoid_s/monoid_rolling_hash.hpp)

• View this file on GitHub
• Last update: 2024-03-24 17:04:51+09:00
• Include: #include "algebra/monoid_s/monoid_rolling_hash.hpp"

clang でコンパイルするときには -std=c++2b をつける

// mint は定義済
#include "algebra/monoid_s/monoid_rolling_hash.hpp"
using mrh = MonoidRollingHash<mint>;
template <> mint mrh::base = 0;

int main() {
    mrh::set_base();
    // code here
}

mrh::set_base(b) とすると基数に b にセットできる

配列を初期化するには mrh::make_element(x) とする

std::vector<std::pair<mint, mint>> seginit;
seginit.push_back(mrh::make_element(x));
SegmentTree<mrh> seg(seginit);

使用例

• ABC298 D
  • set_base() に乱数以外を用いる例
• ABC331 F
  • 1点更新区間回分判定クエリ->反転した文字列も持つ

Code

#pragma once
// MS
template <class Mint> struct MonoidRollingHash {
    using S = std::pair<Mint, Mint>;  // {hash(s), base ^ len(s)}

    static Mint base;

    static void constexpr set_base(Mint b = Mint(0)) {
        if (b == Mint(0)) {
            std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
            std::uniform_int_distribution<uint64_t> rand(1, Mint::mod() - 1);
            base = Mint(rand(mt));
        } else {
            base = b;
        }
    }

    static constexpr S make_element(Mint x) { return {x, base}; }

    static constexpr S op(S a, S b) { return {a.first * b.second + b.first, a.second * b.second}; }
    static constexpr S e() { return {Mint(0), Mint(1)}; }  // {hash(""), base ^ len("")}
};

#line 2 "algebra/monoid_s/monoid_rolling_hash.hpp"
// MS
template <class Mint> struct MonoidRollingHash {
    using S = std::pair<Mint, Mint>;  // {hash(s), base ^ len(s)}

    static Mint base;

    static void constexpr set_base(Mint b = Mint(0)) {
        if (b == Mint(0)) {
            std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
            std::uniform_int_distribution<uint64_t> rand(1, Mint::mod() - 1);
            base = Mint(rand(mt));
        } else {
            base = b;
        }
    }

    static constexpr S make_element(Mint x) { return {x, base}; }

    static constexpr S op(S a, S b) { return {a.first * b.second + b.first, a.second * b.second}; }
    static constexpr S e() { return {Mint(0), Mint(1)}; }  // {hash(""), base ^ len("")}
};

Back to top page