Rolling Hash
(src/string/RollingHash.hpp)

• View this file on GitHub
• Last update: 2024-09-28 01:48:34+09:00
• Include: #include "src/string/RollingHash.hpp"

概要

$\bmod\ 2^{61}-1$ で基数は $\left[2, 2^{61}-1\right)$ の乱数によるRolling Hash．

メンバ関数	効果	時間計算量
build(s)	文字列もしくは数列 $s$ に対する hash table を返す．	$O(|S|)$
get(s)	文字列もしくは数列 $s$ 全体の hash 値をを返す．	$O(|S|)$
query(hash, l, r)	build で生成された hash table である hash をもとにこの列の区間 $[l, r)$ に対応する hash 値を返す．	$O(1)$
combine(h1, h2, h2_len)	前半の hash 値が $h_1$，後半のそれが $h_2$ で後半の長さが h2_len のときに列全体の hash 値を返す．	$O(1)$
lcp(a, l1, r1, b, l2, r2)	hash table $a$ からなる列の $[l_1, r_1)$ の部分文字列と，hash table $b$ からなる列の $[l_2, r_2)$ の部分文字列の LCP の長さを返す．	$O(\log\max(r_1 - l_1, r_2 - l_2))$

問題例

• Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 1) C. Morse Code
  • $\bmod$ の値が小さいとかなりの確率で衝突し，hash 値を 2 つもとうとすると TLE にハマるので，この Rolling Hash が特に有効．

参照

• 安全で爆速なRollingHashの話 - Qiita

Depends on

• Hash (reversible) (src/string/Hash.hpp)

Verified with

• test/aoj/ALDS1_14_B.test.cpp

Code

#pragma once
#include <algorithm>
#include <string>
#include "Hash.hpp"

struct RollingHash {
    using mint = hash_impl::modint;

    RollingHash() : power{mint(1)} {}

    template <typename T> std::vector<mint> build(const T& s) const {
        int n = s.size();
        std::vector<mint> hash(n + 1);
        hash[0] = 0;
        for (int i = 0; i < n; i++) hash[i + 1] = hash[i] * base + s[i];
        return hash;
    }

    template <typename T> mint get(const T& s) const {
        mint res = 0;
        for (const auto& x : s) res = res * base + x;
        return res;
    }

    mint query(const std::vector<mint>& hash, int l, int r) {
        assert(0 <= l && l <= r);
        extend(r - l);
        return hash[r] - hash[l] * power[r - l];
    }

    mint combine(mint h1, mint h2, int h2_len) {
        extend(h2_len);
        return h1 * power[h2_len] + h2;
    }

    int lcp(const std::vector<mint>& a, int l1, int r1, const std::vector<mint>& b, int l2, int r2) {
        int len = std::min(r1 - l1, r2 - l2);
        int lb = 0, ub = len + 1;
        while (ub - lb > 1) {
            int mid = (lb + ub) >> 1;
            (query(a, l1, l1 + mid) == query(b, l2, l2 + mid) ? lb : ub) = mid;
        }
        return lb;
    }

  private:
    const mint base = hash_impl::base;
    std::vector<mint> power;

    inline void extend(int len) {
        if (int(power.size()) > len) return;
        int pre = power.size();
        power.resize(len + 1);
        for (int i = pre - 1; i < len; i++) power[i + 1] = power[i] * base;
    }
};

#line 2 "src/string/RollingHash.hpp"
#include <algorithm>
#include <string>
#line 2 "src/string/Hash.hpp"
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

namespace hash_impl {

static constexpr unsigned long long mod = (1ULL << 61) - 1;

struct modint {
    modint() : _v(0) {}
    modint(long long v) {
        unsigned long long vv = v < 0 ? v + mod : v;
        vv = (vv >> 61) + (vv & mod);
        if (vv >= mod) vv -= mod;
        _v = vv;
    }

    unsigned long long val() const { return _v; }

    modint& operator+=(const modint& rhs) {
        _v += rhs._v;
        if (_v >= mod) _v -= mod;
        return *this;
    }
    modint& operator-=(const modint& rhs) {
        if (_v < rhs._v) _v += mod;
        _v -= rhs._v;
        return *this;
    }
    modint& operator*=(const modint& rhs) {
        __uint128_t t = __uint128_t(_v) * rhs._v;
        t = (t >> 61) + (t & mod);
        if (t >= mod) t -= mod;
        _v = t;
        return *this;
    }
    modint& operator/=(const modint& rhs) { return *this = *this * rhs.inv(); }

    modint operator-() const { return modint() - *this; }

    modint pow(long long n) const {
        assert(0 <= n);
        modint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    modint inv() const { return pow(mod - 2); }

    friend modint operator+(const modint& lhs, const modint& rhs) { return modint(lhs) += rhs; }
    friend modint operator-(const modint& lhs, const modint& rhs) { return modint(lhs) -= rhs; }
    friend modint operator*(const modint& lhs, const modint& rhs) { return modint(lhs) *= rhs; }
    friend modint operator/(const modint& lhs, const modint& rhs) { return modint(lhs) /= rhs; }
    friend bool operator==(const modint& lhs, const modint& rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const modint& lhs, const modint& rhs) { return lhs._v != rhs._v; }
    friend std::ostream& operator<<(std::ostream& os, const modint& rhs) {
        os << rhs._v;
        return os;
    }

  private:
    unsigned long long _v;
};

uint64_t generate_base() {
    std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<uint64_t> rand(2, mod - 1);
    return rand(mt);
}

modint base(generate_base());
std::vector<modint> power{1};

modint get_pow(int n) {
    if (n < int(power.size())) return power[n];
    int m = power.size();
    power.resize(n + 1);
    for (int i = m; i <= n; i++) power[i] = power[i - 1] * base;
    return power[n];
}

};  // namespace hash_impl

struct Hash {
    using mint = hash_impl::modint;
    mint x;
    int len;

    Hash() : x(0), len(0) {}
    Hash(mint x) : x(x), len(1) {}
    Hash(mint x, int len) : x(x), len(len) {}

    Hash& operator+=(const Hash& rhs) {
        x = x * hash_impl::get_pow(rhs.len) + rhs.x;
        len += rhs.len;
        return *this;
    }
    Hash operator+(const Hash& rhs) const { return Hash(*this) += rhs; }
    bool operator==(const Hash& rhs) const { return x == rhs.x and len == rhs.len; }
};

struct ReversibleHash {
    using mint = hash_impl::modint;
    mint x, rx;
    int len;

    ReversibleHash() : x(0), rx(0), len(0) {}
    ReversibleHash(mint x) : x(x), rx(x), len(1) {}
    ReversibleHash(mint x, mint rx, int len) : x(x), rx(rx), len(len) {}

    ReversibleHash rev() const { return ReversibleHash(rx, x, len); }

    ReversibleHash operator+=(const ReversibleHash& rhs) {
        x = x * hash_impl::get_pow(rhs.len) + rhs.x;
        rx = rx + rhs.rx * hash_impl::get_pow(len);
        len += rhs.len;
        return *this;
    }
    ReversibleHash operator+(const ReversibleHash& rhs) const { return ReversibleHash(*this) += rhs; }
    bool operator==(const ReversibleHash& rhs) const { return x == rhs.x and rx == rhs.rx and len == rhs.len; }
};
#line 5 "src/string/RollingHash.hpp"

struct RollingHash {
    using mint = hash_impl::modint;

    RollingHash() : power{mint(1)} {}

    template <typename T> std::vector<mint> build(const T& s) const {
        int n = s.size();
        std::vector<mint> hash(n + 1);
        hash[0] = 0;
        for (int i = 0; i < n; i++) hash[i + 1] = hash[i] * base + s[i];
        return hash;
    }

    template <typename T> mint get(const T& s) const {
        mint res = 0;
        for (const auto& x : s) res = res * base + x;
        return res;
    }

    mint query(const std::vector<mint>& hash, int l, int r) {
        assert(0 <= l && l <= r);
        extend(r - l);
        return hash[r] - hash[l] * power[r - l];
    }

    mint combine(mint h1, mint h2, int h2_len) {
        extend(h2_len);
        return h1 * power[h2_len] + h2;
    }

    int lcp(const std::vector<mint>& a, int l1, int r1, const std::vector<mint>& b, int l2, int r2) {
        int len = std::min(r1 - l1, r2 - l2);
        int lb = 0, ub = len + 1;
        while (ub - lb > 1) {
            int mid = (lb + ub) >> 1;
            (query(a, l1, l1 + mid) == query(b, l2, l2 + mid) ? lb : ub) = mid;
        }
        return lb;
    }

  private:
    const mint base = hash_impl::base;
    std::vector<mint> power;

    inline void extend(int len) {
        if (int(power.size()) > len) return;
        int pre = power.size();
        power.resize(len + 1);
        for (int i = pre - 1; i < len; i++) power[i + 1] = power[i] * base;
    }
};

Back to top page