String/Hash/test_hash1.cpp

• View this file on GitHub
• Last update: 2025-05-30 22:12:29+07:00
• Link: https://oj.vnoi.info/problem/substr

Depends on

• String/Hash/Rolling_Hash.h
• template.h

Code

#include "../../template.h"
#include "Rolling_Hash.h"

/* AC: https://oj.vnoi.info/problem/substr */

void solve() {
    string s1, s2; cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    Hash<int> h1(s1), h2(s2);
    for (int i = 1; i <= n-m+1; i++) {
        if (h1.getHash(i, i+m-1) == h2.getHash(1, m)) {
            cout << i << ' ';
        }
    }
}

#line 2 "template.h"

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MOD (ll)(1e9+7)
#define all(x) (x).begin(),(x).end()
#define unique(x) x.erase(unique(all(x)), x.end())
#define INF32 ((1ull<<31)-1)
#define INF64 ((1ull<<63)-1)
#define inf (ll)1e18

#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int mod = 998244353;

void solve();

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // cin.exceptions(cin.failbit);
    // int t; cin >> t;
    // while(t--)
        solve();
    cerr << "\nTime run: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << '\n';
    return 0;
}
#line 2 "String/Hash/Rolling_Hash.h"

template <typename T>
class Hash {
public:
    static constexpr int base = 331;
    static constexpr int mod = 1'000'000'007;
    vector<T> h, p;

    Hash() {}

    Hash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();
        h = hashStr(s, n);
        p = calc_pow(n);
    }

    T getHash(int l, int r) const {
        T x = (h[r] - 1ll * h[l-1] * p[r-l+1]) % mod;
        return T((x + mod) % mod);
    }

private:
    vector<T> hashStr(const string &s, int n) {
        vector<T> hash(n + 1);
        for (int i = 1; i <= n; i++) {
            int c = s[i - 1] - 'a' + 1;
            hash[i] = (1ll * hash[i-1] * base + c) % mod;
        }
        return hash;
    }

    vector<T> calc_pow(int n) {
        vector<T> P;
        P.emplace_back(1);
        for (int i = 1; i <= n; i++) {
            P.emplace_back((1ll * P[i-1] * base) % mod);
        }
        return P;
    }
};
#line 3 "String/Hash/test_hash1.cpp"

/* AC: https://oj.vnoi.info/problem/substr */

void solve() {
    string s1, s2; cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    Hash<int> h1(s1), h2(s2);
    for (int i = 1; i <= n-m+1; i++) {
        if (h1.getHash(i, i+m-1) == h2.getHash(1, m)) {
            cout << i << ' ';
        }
    }
}

Back to top page