test/aoj/ALDS1_14_B.rolling_hash.test.cpp

• View this file on GitHub
• Last update: 2024-01-07 22:05:53+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

• Rolling Hash (string/rolling_hash.hpp)

Code

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

#include <bits/stdc++.h>

#include "../../string/rolling_hash.hpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string T;
    cin >> T;
    string P;
    cin >> P;
    long long base = RollingHash::generate_base();
    RollingHash rht(T, base);
    RollingHash rhp(P, base);
    for (int i = 0; i + P.size() <= T.size(); ++i) {
        if (rht.query(i, i + P.size()) == rhp.query(0, P.size())) {
            cout << i << "\n";
        }
    }
}

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

#include <bits/stdc++.h>

#line 5 "string/rolling_hash.hpp"

class RollingHash {
   public:
    static long long generate_base() {
        std::random_device rd;
        std::mt19937_64 rng(rd());
        std::uniform_int_distribution<long long> rand(1, mod - 1);
        return rand(rng);
    }

    RollingHash() = default;
    RollingHash(const std::string& s, long long base)
        : RollingHash(std::vector<char>(s.begin(), s.end()), base) {}
    template <typename T>
    RollingHash(const std::vector<T>& s, long long base)
        : base(base), hashed(s.size() + 1), power(s.size() + 1) {
        power[0] = 1;
        for (int i = 0; i < (int)s.size(); ++i) {
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = add(mul(hashed[i], base), s[i]);
        }
    }

    long long query(int l, int r) const {
        return add(hashed[r], mod - mul(hashed[l], power[r - l]));
    }

    long long combine(long long h1, long long h2, int len2) const {
        return add(mul(h1, power[len2]), h2);
    }

    void push_back(char c) {
        power.push_back(mul(power.back(), base));
        hashed.push_back(add(mul(hashed.back(), base), c));
    }

   private:
    static constexpr long long mod = (1LL << 61) - 1;

    static inline long long add(long long a, long long b) {
        if ((a += b) >= mod) a -= mod;
        return a;
    }

    static inline long long mul(long long a, long long b) {
        __int128_t c = (__int128_t)a * b;
        return add(c >> 61, c & mod);
    }

    const long long base;
    std::vector<long long> hashed, power;
};
#line 7 "test/aoj/ALDS1_14_B.rolling_hash.test.cpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string T;
    cin >> T;
    string P;
    cin >> P;
    long long base = RollingHash::generate_base();
    RollingHash rht(T, base);
    RollingHash rhp(P, base);
    for (int i = 0; i + P.size() <= T.size(); ++i) {
        if (rht.query(i, i + P.size()) == rhp.query(0, P.size())) {
            cout << i << "\n";
        }
    }
}

Back to top page