library/sequence/RollingHash.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/sequence/RollingHash.hpp"
Link: View error logs on GitHub Actions
Link: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6

Depends on

Verified with

test/AOJ/ALDS1_14_B.test.cpp

Code

// reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
#pragma once
#include "library/mod/Modint61.hpp"
#include "library/sequence/ForString.hpp"

#include <random>
#include <vector>

std::random_device rollonghash_rnd;
std::mt19937 rollonghash_mt(rollonghash_rnd());

template <typename CHAR = char, typename MINT = Modint61> class RollingHash {
    using ll = long long;
    static constexpr ll mod = (1LL << 61) - 1;
    // using T = conditional_t< less<ll>(mod,ll(
    // std::numeric_limits<int>::max())), int, ll>;
    using T = ll;
    inline static const MINT base = MINT::raw(rollonghash_mt() % (mod - 2) + 2);

    int n;
    std::vector<MINT> hash;

  public:
    static std::vector<MINT> power;

    RollingHash() = default;
    RollingHash(const std::vector<CHAR> &v) : n(v.size()), hash(n + 1, 0) {
        if (!power.size())
            power.push_back(1);
        for (int i = 0; i < n; i++)
            hash[i + 1] = nxt_hash(hash[i], v[i]);

        if (power.size() <= n) {
            int sz = std::max(int(2 * power.size()), n + 1);
            power.reserve(sz);
            while (power.size() < sz)
                power.push_back(power.back() * base);
        }
    }

    static MINT nxt_hash(MINT x, CHAR c) { return (x * base) + MINT::raw(c); }

    T get_hash(int l = 0, int r = -1) {
        if (r < 0)
            r = n;
        return (hash[r] - hash[l] * power[r - l]).v;
    }

    static T full_hash(const std::vector<CHAR> &v) {
        MINT res = 0;
        for (const char &c : v)
            res = nxt_hash(res, c);
        return res.v;
    }
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: library/sequence/RollingHash.hpp: line 2: #pragma once found in a non-first line