verify/string/rolling_hash.test.cpp

View this file on GitHub
Last update: 2024-08-27 02:34:27+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <iostream>

#include "string/rolling_hash.hpp"

int main() {
    std::string T, P;
    std::cin >> T >> P;
    RollingHash<mint261> rh;
    auto rht = rh.build(T);
    auto rhp = rh.build(P);
    for (int i = 0; i + P.size() <= T.size(); i++) {
        if (rh.prod(rht, i, i + P.size()) == rh.prod(rhp, 0, P.size())) {
            std::cout << i << '\n';
        }
    }
    return 0;
}

#line 1 "verify/string/rolling_hash.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <iostream>

#line 2 "string/rolling_hash.hpp"

#line 2 "math/modint261.hpp"

#include <cassert>

struct Modint261 {
    static constexpr unsigned long long m = (1ULL << 61) - 1;
    using mint = Modint261;
    unsigned long long _v;

    static constexpr long long mod() { return m; }
    static constexpr unsigned long long umod() { return m; }

    Modint261() : _v(0ULL) {}

    template <class T> Modint261(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned long long)(x);
    }

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

    mint &operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint &operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint &operator+=(const mint &rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint &operator*=(const mint &rhs) {
        __uint128_t z = _v;
        z *= rhs._v;
        z = (z >> 61) + (z & umod());
        if (z >= umod()) z -= umod();
        _v = (unsigned long long)z;
        return *this;
    }
    mint &operator/=(const mint &rhs) { return (*this *= rhs.inv()); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(n >= 0);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    mint inv() const { return pow(umod() - 2); }

    friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
    friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
    friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
    friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
    friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; }
    friend std::ostream &operator<<(std::ostream &os, const mint &v) { return os << v.val(); }
};
using mint261 = Modint261;
#line 4 "string/rolling_hash.hpp"

#include <algorithm>
#line 7 "string/rolling_hash.hpp"
#include <chrono>
#include <random>
#include <vector>

// Rolling Hash
template <class Mint> struct RollingHash {
    std::vector<Mint> pwr;
    const Mint base;

    RollingHash(const int n_max = 0, Mint base = generate_base()) : base(base) {
        pwr.resize(1, Mint(1));
        if (n_max > 0) extend(n_max);
    }

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

    void extend(int m = -1) {
        const int n = (int)(pwr.size());  // n >= 1
        if (m == -1) m = n * 2;           // m >= 2
        if (m > Mint::mod()) m = Mint::mod();
        if (n >= m) return;
        pwr.resize(m);
        for (int i = n; i < m; i++) pwr[i] = pwr[i - 1] * base;
    }

    // return base ^ n
    Mint power(const int n) {
        assert(n >= 0);
        while (n >= (int)(pwr.size())) extend();
        return pwr[n];
    }

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

    std::vector<Mint> build(const std::string& s) const {
        const int n = (int)(s.size());
        std::vector<int> s2(n);
        for (int i = 0; i < n; i++) s2[i] = s[i];
        return build(s2);
    }

    Mint prod(const std::vector<Mint>& hs, const int l, const int r) {
        assert(0 <= l and l <= r and r <= (int)(hs.size()));
        return hs[r] - hs[l] * power(r - l);
    }

    Mint combine(Mint h1, Mint h2, int h2len) { return h1 * power(h2len) + h2; }
};
#line 6 "verify/string/rolling_hash.test.cpp"

int main() {
    std::string T, P;
    std::cin >> T >> P;
    RollingHash<mint261> rh;
    auto rht = rh.build(T);
    auto rhp = rh.build(P);
    for (int i = 0; i + P.size() <= T.size(); i++) {
        if (rh.prod(rht, i, i + P.size()) == rh.prod(rhp, 0, P.size())) {
            std::cout << i << '\n';
        }
    }
    return 0;
}