Rolling Hash 2D
(src/string/RollingHash2D.hpp)

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

概要

問題例

• 2023牛客暑期多校训练营3 G - Beautiful Matrix

Depends on

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

Verified with

• test/aoj/ALDS1_14_C.test.cpp

Code

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

struct RollingHash2D {
    using mint = hash_impl::modint;

    static inline 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, hash_impl::mod - 1);
        return rand(mt);
    }

    RollingHash2D(uint64_t base0 = generate_base(), uint64_t base1 = generate_base()) {
        basis[0] = base0;
        basis[1] = base1;
        power[0].assign(1, 1);
        power[1].assign(1, 1);
    }

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

    template <typename T> mint get(const T& s) const {
        mint res = 0;
        for (int i = 0; i < int(s.size()); i++) {
            mint sum = 0;
            for (const auto& x : s[i]) sum = sum * basis[1] + x;
            res = res * basis[0] + sum;
        }
        return res;
    }

    mint query(const std::vector<std::vector<mint>>& hash, int xl, int xr, int yl, int yr) {
        assert(0 <= xl and xl <= xr and 0 <= yl and yl <= yr);
        extend(0, xr - xl);
        extend(1, yr - yl);
        return hash[xr][yr] - hash[xl][yr] * power[0][xr - xl] - hash[xr][yl] * power[1][yr - yl] +
               hash[xl][yl] * power[0][xr - xl] * power[1][yr - yl];
    }

  private:
    mint basis[2];
    std::vector<mint> power[2];

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

#line 2 "src/string/RollingHash2D.hpp"
#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 4 "src/string/RollingHash2D.hpp"

struct RollingHash2D {
    using mint = hash_impl::modint;

    static inline 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, hash_impl::mod - 1);
        return rand(mt);
    }

    RollingHash2D(uint64_t base0 = generate_base(), uint64_t base1 = generate_base()) {
        basis[0] = base0;
        basis[1] = base1;
        power[0].assign(1, 1);
        power[1].assign(1, 1);
    }

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

    template <typename T> mint get(const T& s) const {
        mint res = 0;
        for (int i = 0; i < int(s.size()); i++) {
            mint sum = 0;
            for (const auto& x : s[i]) sum = sum * basis[1] + x;
            res = res * basis[0] + sum;
        }
        return res;
    }

    mint query(const std::vector<std::vector<mint>>& hash, int xl, int xr, int yl, int yr) {
        assert(0 <= xl and xl <= xr and 0 <= yl and yl <= yr);
        extend(0, xr - xl);
        extend(1, yr - yl);
        return hash[xr][yr] - hash[xl][yr] * power[0][xr - xl] - hash[xr][yl] * power[1][yr - yl] +
               hash[xl][yl] * power[0][xr - xl] * power[1][yr - yl];
    }

  private:
    mint basis[2];
    std::vector<mint> power[2];

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

Back to top page