monoid_rolling_hash
(algebra/monoid/monoid_rolling_hash.hpp)

• View this file on GitHub
• Last update: 2026-04-11 00:41:57+09:00
• Include: #include "algebra/monoid/monoid_rolling_hash.hpp"

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

// mint は定義済
#include "algebra/monoid/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点更新区間回分判定クエリ->反転した文字列も持つ

Verified with

• segment_tree/test/segment_tree_rolling_hash.test.cpp

Code

#pragma once

#include <chrono>
#include <cstdint>
#include <random>
#include <utility>

template <class Mint> struct Hash {
    // {hash(s), base ^ len(s)}
    Mint hash;
    Mint power;
    friend std::ostream& operator<<(std::ostream& os, const Hash& v) {
        return os << v.hash << ", " << v.power;
    }
};

template <class Mint> struct MonoidRollingHash {
    using value_type = Hash<Mint>;

    static Mint base;

    static void 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 value_type make_element(Mint x) { return {x, base}; }

    static constexpr value_type operation(const value_type& a,
                                          const value_type& b) {
        return {a.hash * b.power + b.hash, a.power * b.power};
    }
    static constexpr value_type identity() {
        // {hash(""), base ^ len("")}
        return {Mint(0), Mint(1)};
    }

    static constexpr bool commutative = false;
};

#line 2 "algebra/monoid/monoid_rolling_hash.hpp"

#include <chrono>
#include <cstdint>
#include <random>
#include <utility>

template <class Mint> struct Hash {
    // {hash(s), base ^ len(s)}
    Mint hash;
    Mint power;
    friend std::ostream& operator<<(std::ostream& os, const Hash& v) {
        return os << v.hash << ", " << v.power;
    }
};

template <class Mint> struct MonoidRollingHash {
    using value_type = Hash<Mint>;

    static Mint base;

    static void 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 value_type make_element(Mint x) { return {x, base}; }

    static constexpr value_type operation(const value_type& a,
                                          const value_type& b) {
        return {a.hash * b.power + b.hash, a.power * b.power};
    }
    static constexpr value_type identity() {
        // {hash(""), base ^ len("")}
        return {Mint(0), Mint(1)};
    }

    static constexpr bool commutative = false;
};

Back to top page