library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Rolling Hash
(String/rollinghash.hpp)

• View this file on GitHub
• Last update: 2025-05-25 16:11:40+09:00
• Include: #include "String/rollinghash.hpp"

Depends on

• Hash (Math/hash.hpp)
• Random (Utility/random.hpp)

Code

#pragma once
#include "Utility/random.hpp"
#include "Math/hash.hpp"

struct RollingHash {
    using ull = unsigned long long;
    const Hash base;
    vector<Hash> hashed, power;

    static inline ull genbase() {
        return Random::get(ull(0x1fffffffffffffff));
    }
    RollingHash(Hash base) : base(base) {}

    template <typename STR> void build(const STR &s) {
        int n = s.size();
        hashed.assign(n + 1, 0);
        power.assign(n + 1, 0);
        power[0] = 1;
        for (ll i = 0; i < n; i++) {
            power[i + 1] = power[i] * base;
            hashed[i + 1] = hashed[i] * base + s[i];
        }
    }

    Hash get(ll l, ll r) const {
        return hashed[r] - hashed[l] * power[r - l];
    }

    Hash connect(Hash h1, Hash h2, ll h2len) const {
        return h1 * power[h2len] + h2;
    }

    template <typename STR> void connect(const STR &s) {
        ll n = hashed.size() - 1, m = s.size();
        hashed.resize(n + m + 1);
        power.resize(n + m + 1);
        for (ll i = n; i < n + m; i++) {
            power[i + 1] = power[i] * base;
            hashed[i + 1] = hashed[i] * base + s[i - n];
        }
    }

    ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) {
        ll len = min(r1 - l1, r2 - l2);
        ll low = -1, high = len + 1;
        while (high - low > 1) {
            ll mid = (low + high) / 2;
            if (get(l1, l1 + mid) == b.get(l2, l2 + mid))
                low = mid;
            else
                high = mid;
        }
        return low;
    }
};

/**
 * @brief Rolling Hash
 */

#line 2 "Utility/random.hpp"

namespace Random {
mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count());
using u64 = unsigned long long;
u64 get() {
    return randgen();
}
template <typename T> T get(T L) { // [0,L]

    return get() % (L + 1);
}
template <typename T> T get(T L, T R) { // [L,R]

    return get(R - L) + L;
}
double uniform() {
    return double(get(1000000000)) / 1000000000;
}
string str(int n) {
    string ret;
    rep(i, 0, n) ret += get('a', 'z');
    return ret;
}
template <typename Iter> void shuffle(Iter first, Iter last) {
    if (first == last)
        return;
    int len = 1;
    for (auto it = first + 1; it != last; it++) {
        len++;
        int j = get(0, len - 1);
        if (j != len - 1)
            iter_swap(it, first + j);
    }
}
template <typename T> vector<T> select(int n, T L, T R) { // [L,R]

    if (n * 2 >= R - L + 1) {
        vector<T> ret(R - L + 1);
        iota(ALL(ret), L);
        shuffle(ALL(ret));
        ret.resize(n);
        return ret;
    } else {
        unordered_set<T> used;
        vector<T> ret;
        while (SZ(used) < n) {
            T x = get(L, R);
            if (!used.count(x)) {
                used.insert(x);
                ret.push_back(x);
            }
        }
        return ret;
    }
}

void relabel(int n, vector<pair<int, int>> &es) {
    shuffle(ALL(es));
    vector<int> ord(n);
    iota(ALL(ord), 0);
    shuffle(ALL(ord));
    for (auto &[u, v] : es)
        u = ord[u], v = ord[v];
}
template <bool directed, bool multi, bool self>
vector<pair<int, int>> genGraph(int n, int m) {
    vector<pair<int, int>> cand, es;
    rep(u, 0, n) rep(v, 0, n) {
        if (!self and u == v)
            continue;
        if (!directed and u > v)
            continue;
        cand.push_back({u, v});
    }
    if (m == -1)
        m = get(SZ(cand));
    // chmin(m, SZ(cand));

    vector<int> ord;
    if (multi)
        rep(_, 0, m) ord.push_back(get(SZ(cand) - 1));
    else {
        ord = select(m, 0, SZ(cand) - 1);
    }
    for (auto &i : ord)
        es.push_back(cand[i]);
    relabel(n, es);
    return es;
}
vector<pair<int, int>> genTree(int n) {
    vector<pair<int, int>> es;
    rep(i, 1, n) es.push_back({get(i - 1), i});
    relabel(n, es);
    return es;
}
}; // namespace Random


/**
 * @brief Random
 */
#line 2 "Math/hash.hpp"

struct Hash {
    static constexpr ull mod = 0x1fffffffffffffff;
    ull v;
    static constexpr ull get_mod() {
        return mod;
    }
    constexpr ull inv() const {
        assert(v != 0);
        ull x = v, y = mod, p = 1, q = 0, t = 0, tmp = 0;
        while (y > 0) {
            t = x / y;
            x -= t * y, p -= t * q;
            tmp = x, x = y, y = tmp;
            tmp = p, p = q, q = tmp;
        }
        if (p < 0)
            p += mod;
        return p;
    }
    constexpr Hash(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
    Hash operator-() const {
        return Hash() - *this;
    }
    Hash pow(ull t) {
        Hash res = 1, b = *this;
        while (t) {
            if (t & 1)
                res *= b;
            b *= b;
            t >>= 1;
        }
        return res;
    }
    Hash &operator+=(const Hash &x) {
        if ((v += x.v) >= mod)
            v -= mod;
        return *this;
    }
    Hash &operator-=(const Hash &x) {
        if ((v += mod - x.v) >= mod)
            v -= mod;
        return *this;
    }
    Hash &operator*=(const Hash &x) {
        u128 ans = u128(v) * x.v;
        ans = (ans >> 61) + (ans & mod);
        if (ans >= mod)
            ans -= mod;
        v = ans;
        return *this;
    }
    Hash &operator/=(const Hash &x) {
        v = ull(v) * x.inv() % mod;
        return *this;
    }
    Hash operator+(const Hash &x) const {
        return Hash(*this) += x;
    }
    Hash operator-(const Hash &x) const {
        return Hash(*this) -= x;
    }
    Hash operator*(const Hash &x) const {
        return Hash(*this) *= x;
    }
    Hash operator/(const Hash &x) const {
        return Hash(*this) /= x;
    }
    bool operator==(const Hash &x) const {
        return v == x.v;
    }
    bool operator!=(const Hash &x) const {
        return v != x.v;
    }
    // mapに載せる時用
    bool operator<(const Hash &x) const {
        return v < x.v;
    }
    bool operator<=(const Hash &x) const {
        return v <= x.v;
    }
    bool operator>(const Hash &x) const {
        return v > x.v;
    }
    bool operator>=(const Hash &x) const {
        return v >= x.v;
    }
    friend istream &operator>>(istream &is, Hash &x) {
        return is >> x.v;
    }
    friend ostream &operator<<(ostream &os, const Hash &x) {
        return os << x.v;
    }
};

void rd(Hash &x) {
    fastio::rd(x.v);
}

/**
 * @brief Hash
 */
#line 4 "String/rollinghash.hpp"

struct RollingHash {
    using ull = unsigned long long;
    const Hash base;
    vector<Hash> hashed, power;

    static inline ull genbase() {
        return Random::get(ull(0x1fffffffffffffff));
    }
    RollingHash(Hash base) : base(base) {}

    template <typename STR> void build(const STR &s) {
        int n = s.size();
        hashed.assign(n + 1, 0);
        power.assign(n + 1, 0);
        power[0] = 1;
        for (ll i = 0; i < n; i++) {
            power[i + 1] = power[i] * base;
            hashed[i + 1] = hashed[i] * base + s[i];
        }
    }

    Hash get(ll l, ll r) const {
        return hashed[r] - hashed[l] * power[r - l];
    }

    Hash connect(Hash h1, Hash h2, ll h2len) const {
        return h1 * power[h2len] + h2;
    }

    template <typename STR> void connect(const STR &s) {
        ll n = hashed.size() - 1, m = s.size();
        hashed.resize(n + m + 1);
        power.resize(n + m + 1);
        for (ll i = n; i < n + m; i++) {
            power[i + 1] = power[i] * base;
            hashed[i + 1] = hashed[i] * base + s[i - n];
        }
    }

    ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) {
        ll len = min(r1 - l1, r2 - l2);
        ll low = -1, high = len + 1;
        while (high - low > 1) {
            ll mid = (low + high) / 2;
            if (get(l1, l1 + mid) == b.get(l2, l2 + mid))
                low = mid;
            else
                high = mid;
        }
        return low;
    }
};

/**
 * @brief Rolling Hash
 */

Back to top page