cplib-cpp

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

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: string/test/rolling_hash_2d.aoj.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_C"
#include "../../number/modint_mersenne61.hpp"
#include "../rolling_hash_2d.hpp"

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (auto &s : S) cin >> s;

    int X, Y;
    cin >> X >> Y;
    vector<string> T(X);
    for (auto &t : T) cin >> t;

    const ModIntMersenne61 b1(418672), b2(956731);

    rolling_hash_2d<ModIntMersenne61> rhs(S, b1, b2);

    const auto tgt = rolling_hash_2d<ModIntMersenne61>(T, b1, b2).get(0, X, 0, Y);

    for (int i = 0; i + X <= H; ++i) {
        for (int j = 0; j + Y <= W; ++j) {
            if (rhs.get(i, i + X, j, j + Y) == tgt) cout << i << ' ' << j << '\n';
        }
    }
}
#line 1 "string/test/rolling_hash_2d.aoj.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_C"
#line 2 "number/modint_mersenne61.hpp"
#include <cassert>
#include <chrono>
#include <random>

// F_p, p = 2^61 - 1
// https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
class ModIntMersenne61 {
    static const long long md = (1LL << 61) - 1;
    long long _v;

    inline unsigned hi() const noexcept { return _v >> 31; }
    inline unsigned lo() const noexcept { return _v & ((1LL << 31) - 1); }

public:
    static long long mod() { return md; }

    ModIntMersenne61() : _v(0) {}
    // 0 <= x < md * 2
    explicit ModIntMersenne61(long long x) : _v(x >= md ? x - md : x) {
        assert(0 <= x and x < md * 2);
    }

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

    ModIntMersenne61 operator+(const ModIntMersenne61 &x) const {
        return ModIntMersenne61(_v + x._v);
    }

    ModIntMersenne61 operator-(const ModIntMersenne61 &x) const {
        return ModIntMersenne61(_v + md - x._v);
    }

    ModIntMersenne61 operator*(const ModIntMersenne61 &x) const {
        using ull = unsigned long long;

        ull uu = (ull)hi() * x.hi() * 2;
        ull ll = (ull)lo() * x.lo();
        ull lu = (ull)hi() * x.lo() + (ull)lo() * x.hi();

        ull sum = uu + ll + ((lu & ((1ULL << 30) - 1)) << 31) + (lu >> 30);
        ull reduced = (sum >> 61) + (sum & ull(md));
        return ModIntMersenne61(reduced);
    }

    ModIntMersenne61 pow(long long n) const {
        assert(n >= 0);
        ModIntMersenne61 ans(1), tmp = *this;
        while (n) {
            if (n & 1) ans *= tmp;
            tmp *= tmp, n >>= 1;
        }
        return ans;
    }

    ModIntMersenne61 inv() const { return pow(md - 2); }

    ModIntMersenne61 operator/(const ModIntMersenne61 &x) const { return *this * x.inv(); }

    ModIntMersenne61 operator-() const { return ModIntMersenne61(md - _v); }
    ModIntMersenne61 &operator+=(const ModIntMersenne61 &x) { return *this = *this + x; }
    ModIntMersenne61 &operator-=(const ModIntMersenne61 &x) { return *this = *this - x; }
    ModIntMersenne61 &operator*=(const ModIntMersenne61 &x) { return *this = *this * x; }
    ModIntMersenne61 &operator/=(const ModIntMersenne61 &x) { return *this = *this / x; }

    ModIntMersenne61 operator+(unsigned x) const { return ModIntMersenne61(this->_v + x); }

    bool operator==(const ModIntMersenne61 &x) const { return _v == x._v; }
    bool operator!=(const ModIntMersenne61 &x) const { return _v != x._v; }
    bool operator<(const ModIntMersenne61 &x) const { return _v < x._v; } // To use std::map

    template <class OStream> friend OStream &operator<<(OStream &os, const ModIntMersenne61 &x) {
        return os << x._v;
    }

    static ModIntMersenne61 randgen(bool force_update = false) {
        static ModIntMersenne61 b(0);
        if (b == ModIntMersenne61(0) or force_update) {
            std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count());
            std::uniform_int_distribution<long long> d(1, ModIntMersenne61::mod());
            b = ModIntMersenne61(d(mt));
        }
        return b;
    }
};
#line 2 "string/rolling_hash_2d.hpp"
#include <string>
#include <vector>

// Rolling Hash (Rabin-Karp), 2dim
template <typename V> struct rolling_hash_2d {
    const V Bx, By;
    std::vector<V> powx, powy; // powx[i] = Bx^i
    std::vector<std::vector<V>> hash;

    void gen_pow(int h, int w) {
        powx.assign(h + 1, V(1));
        for (int i = 1; i <= h; ++i) powx.at(i) = powx.at(i - 1) * Bx;
        powy.assign(w + 1, V(1));
        for (int i = 1; i <= w; ++i) powy.at(i) = powy.at(i - 1) * By;
    }

    inline V _at(int x, int y) const noexcept {
        if (x < 0 or x >= int(hash.size())) return V();
        if (y < 0 or y >= int(hash[x].size())) return V();
        return hash[x][y];
    }

    template <typename Int> void build(const std::vector<std::vector<Int>> &s) {
        const int H = s.size(), W = H ? s.at(0).size() : 0;
        gen_pow(H, W);

        hash.assign(H, std::vector<V>(W, V()));
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) hash[i][j] = _at(i, j - 1) * By + s[i][j];
        }

        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) hash[i][j] = hash[i][j] + _at(i - 1, j) * Bx;
        }
    }

    template <typename Int>
    rolling_hash_2d(const std::vector<std::vector<Int>> &s, V bx, V by) : Bx(bx), By(by) {
        build(s);
    }

    rolling_hash_2d(const std::vector<std::string> &m, V bx, V by) : Bx(bx), By(by) {
        std::vector<std::vector<int>> v_;
        for (const auto &s : m) {
            v_.push_back({});
            for (char c : s) v_.back().push_back(int(c));
        }
        build(v_);
    }

    V get(int xl, int xr, int yl, int yr) const {
        return _at(xr - 1, yr - 1) - _at(xl - 1, yr - 1) * powx[xr - xl] -
               _at(xr - 1, yl - 1) * powy[yr - yl] +
               _at(xl - 1, yl - 1) * powx[xr - xl] * powy[yr - yl];
    }
};
#line 4 "string/test/rolling_hash_2d.aoj.test.cpp"

#include <iostream>
#line 8 "string/test/rolling_hash_2d.aoj.test.cpp"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (auto &s : S) cin >> s;

    int X, Y;
    cin >> X >> Y;
    vector<string> T(X);
    for (auto &t : T) cin >> t;

    const ModIntMersenne61 b1(418672), b2(956731);

    rolling_hash_2d<ModIntMersenne61> rhs(S, b1, b2);

    const auto tgt = rolling_hash_2d<ModIntMersenne61>(T, b1, b2).get(0, X, 0, Y);

    for (int i = 0; i + X <= H; ++i) {
        for (int j = 0; j + Y <= W; ++j) {
            if (rhs.get(i, i + X, j, j + Y) == tgt) cout << i << ' ' << j << '\n';
        }
    }
}
Back to top page