string hashing with pair

problem link:https://cses.fi/problemset/task/1753/

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int mx = 1e6 + 5;
pair<int, int> pw[mx + 5], invPw[mx + 5];
inline void normal(ll &a, ll MOD) {
    a %= MOD;
    (a < 0) && (a += MOD);
}
inline ll modMul(ll a, ll b, ll MOD) {
    a %= MOD, b %= MOD;
    normal(a, MOD), normal(b, MOD);
    return (a * b) % MOD;
}
inline ll modPow(ll b, ll p, ll MOD) {
    ll r = 1;
    while (p) {
        if (p & 1)
            r = modMul(r, b, MOD);
        b = modMul(b, b, MOD);
        p >>= 1;
    }
    return r;
}
inline ll modInverse(ll a, ll MOD) { return modPow(a, MOD - 2, MOD); }
int p1 = 31, p2 = 37, MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
void pw_cal() {
    pw[0] = {1, 1};
    for (int i = 1; i <= mx; i++) {
        pw[i].first = 1LL * pw[i - 1].first * p1 % MOD1;
        pw[i].second = 1LL * pw[i - 1].second * p2 % MOD2;
    }
    int invp1 = modInverse(p1, MOD1);
    int invp2 = modInverse(p2, MOD2);
    invPw[0] = {1, 1};
    for (int i = 1; i <= mx; i++) {
        invPw[i].first = 1LL * invPw[i - 1].first * invp1 % MOD1;
        invPw[i].second = 1LL * invPw[i - 1].second * invp2 % MOD2;
    }
}
pair<int, int> string_hash(string s) {
    pair<int, int> hs({0, 0});
    for (int i = 0; i < s.size(); i++) {
        hs.first += 1LL * (s[i] - 'a' + 1) * pw[i].first % MOD1;
        hs.first %= MOD1;
        hs.second += 1LL * (s[i] - 'a' + 1) * pw[i].second % MOD2;
        hs.second %= MOD2;
    }
    return hs;
}
pair<int, int> pre[mx + 5];
void build(string s) {
    int n = s.size();
    for (int i = 0; i < n; i++) {
        pre[i].first = 1LL * (s[i] - 'a' + 1) * pw[i].first % MOD1;
        pre[i].second = 1LL * (s[i] - 'a' + 1) * pw[i].second % MOD2;
        if (i)pre[i].first = (pre[i].first + pre[i - 1].first) % MOD1;
        if (i)pre[i].second = (pre[i].second + pre[i - 1].second) % MOD2;
    }
}
pair<int, int> getHash(int i, int j) {
    assert(i <= j);
    pair<int, int> hs({0, 0});
    hs.first = pre[j].first;
    if (i)hs.first = (hs.first - pre[i - 1].first + MOD1) % MOD1;
    hs.first = 1LL * hs.first * invPw[i].first % MOD1;
    hs.second = pre[j].second;
    if (i)hs.second = (hs.second - pre[i - 1].second + MOD2) % MOD2;
    hs.second = 1LL * hs.second * invPw[i].second % MOD2;
    return hs;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    pw_cal();
    string s1, s2;
    cin >> s1 >> s2;
    build(s1);
    pair<int, int> check = string_hash(s2);
    int cnt = 0;
    int m = s2.size();
    for (int i = 0; i + m - 1 < s1.size(); i++) {
        cnt += getHash(i, i + m - 1) == check;
    }
    cout << cnt << endl;
    return 0;
}