String Matching using double hashing(and more problem)

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;

int pw1[mx + 5], pw2[mx + 5], invPw1[mx + 5], invPw2[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() {
    pw1[0] = 1;
    for (int i = 1; i <= mx; i++) {
        pw1[i] = 1LL * pw1[i - 1] * p1 % MOD1;
    }
    pw2[0] = 1;
    for (int i = 1; i <= mx; i++) {
        pw2[i] = 1LL * pw2[i - 1] * p2 % MOD2;
    }
    int invp1 = modInverse(p1, MOD1);
    int invp2 = modInverse(p2, MOD2);
    invPw1[0] = 1, invPw2[0] = 1;
    for (int i = 1; i <= mx; i++) {
        invPw1[i] = 1LL * invPw1[i - 1] * invp1 % MOD1;
    }
    for (int i = 1; i <= mx; i++) {
        invPw2[i] = 1LL * invPw2[i - 1] * invp2 % MOD2;
    }
}

pair<int, int> string_hash(string s) {
    int res1 = 0;
    for (int i = 0; i < s.size(); i++) {
        res1 += 1LL * (s[i] - 'a' + 1) * pw1[i] % MOD1;
        res1 %= MOD1;
    }
    int res2 = 0;
    for (int i = 0; i < s.size(); i++) {
        res2 += 1LL * (s[i] - 'a' + 1) * pw2[i] % MOD2;
        res2 %= MOD2;
    }
    return {res1, res2};
}

int pre1[mx + 5], pre2[mx + 5];

void build(string s) {
    int n = s.size();
    for (int i = 0; i < n; i++) {
        pre1[i] = 1LL * (s[i] - 'a' + 1) * pw1[i] % MOD1;
        pre2[i] = 1LL * (s[i] - 'a' + 1) * pw2[i] % MOD2;
        if (i)pre1[i] = (pre1[i] + pre1[i - 1]) % MOD1;
        if (i)pre2[i] = (pre2[i] + pre2[i - 1]) % MOD2;
    }
}

pair<int, int> getHash(int i, int j) {
    assert(i <= j);
    int hs1 = pre1[j];
    if (i)hs1 = (hs1 - pre1[i - 1] + MOD1) % MOD1;
    hs1 = 1LL * hs1 * invPw1[i] % MOD1;
    int hs2 = pre2[j];
    if (i)hs2 = (hs2 - pre2[i - 1] + MOD2) % MOD2;
    hs2 = 1LL * hs2 * invPw2[i] % MOD2;
    return {hs1, hs2};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    pw_cal();
    string s1, s2;
    cin >> s1 >> s2;
    build(s1);
    int ans = 0;
    int m = s2.size();
    pair<int, int> check = string_hash(s2);
    for (int i = 0; i + m - 1 < s1.size(); i++) {
        ans += (getHash(i, i + m - 1) == check);
    }
    cout << ans << '\n';
    return 0;
}



//// problem:emon ekta string thakbe jekhane find korte hobe koto gula substring diye oi string generate kora jay.
abababab->ab



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    pw_cal();
    string s1;
    cin >> s1;
    build(s1);
    int n = s1.size();
    int cnt = 1;
    for (int len = 1; len <= n / 2; len++) {
        bool ok = true;
        for (int i = 0; i + len - 1 < n; i += len) {
            ok &= getHash(i, i + len - 1) == getHash(0, len - 1);
        }
        if (ok) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


////  problem:find the largest string that occurs more than k times:
abbccbbc->length=3.->(bbc)->k=2


int n;

int check(int m) {
    map<pair<int, int>, int> mp;
    for (int i = 0; i + m - 1 < n; i++) {
        mp[getHash(i, i + m - 1)]++;
    }
    int mx = 0;
    for (auto[x, y]:mp) {
        mx = max(mx, y);
    }
    return mx;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    pw_cal();
    string s;
    cin >> s;
    build(s);
    n = s.size();
    int k;
    cin >> k;
    int left = 1, right = n;
    int res = -1;
    while (left <= right) {
        int md = (left + right) >> 1;
        if (check(md) >= k) {
            left = md + 1;
            res = md;
        } else {
            right = md - 1;
        }
    }
    cout << res << endl;
    return 0;
}