src/string/rollinghash.hpp

• View this file on GitHub
• Last update: 2021-12-30 20:52:19+09:00
• Include: #include "src/string/rollinghash.hpp"

Depends on

• src/base.hpp
• src/math/comb.hpp
• src/math/modint61.hpp
• src/util/random.hpp

Verified with

• src/rollinghash_zalgo.test.cpp

Code

#pragma once

#include "math/comb.hpp"
#include "math/modint61.hpp"
#include "util/random.hpp"

struct H {
  private:
    static ModInt61 B;
    static ModInt61 iB;
    static V<ModInt61> powB, powiB;

  public:
    static void init(int n) {
        powB = powTable(n, B);
        powiB = powTable(n, iB);
    }
    int le = 0;
    ModInt61 h;
    H() : le(0), h(0) {}
    H(int _le, ModInt61 _h) : le(_le), h(_h) {}
    H(int c) : le(1), h(c) {}
    // H(l) + H(r) = H(lr)
    H operator+(const H& r) const { return H{le + r.le, h + r.h * powB[le]}; }
    H& operator+=(const H& r) { return *this = *this + r; }

    bool operator==(const H& r) const { return le == r.le && h == r.h; }
    bool operator!=(const H& r) const { return !(*this == r); }
    // H(lr).strip_left(H(l)) = H(r)
    H strip_left(const H& l) const {
        return H{le - l.le, (h - l.h) * powiB[l.le]};
    }
    // H(lr).strip_right(H(r)) = H(l)
    H strip_right(const H& r) const {
        return H{le - r.le, h - r.h * powB[le - r.le]};
    }
};
ModInt61 H::B =
    ModInt61(global_runtime_gen().uniform(0ULL, ModInt61::get_mod() - 1));
ModInt61 H::iB = H::B.inv();
V<ModInt61> H::powB, H::powiB;

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/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.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: math/comb.hpp: line -1: no such header

Back to top page