Cod sursa(job #2963289)

Utilizator MR0L3eXMaracine Constantin Razvan MR0L3eX Data 10 ianuarie 2023 19:02:44
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include "bits/stdc++.h"

using namespace std;

#if defined(ONPC)
#include "bits/debug.h"
#endif

using i64 = long long;

#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN = 3e6;

int Add(int a, int b, int mod) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

int Mul(int a, int b, int mod) {
    return (i64) a * b % mod;
}

int Sub(int a, int b, int mod) {
    a -= b;
    if (a < 0) a += mod;
    return a;
}

int binpow(int b, int e, int mod) {
    int res = 1;
    for (; e > 0; e /= 2, b = Mul(b, b, mod)) {
        if (e & 1) res = Mul(res, b, mod);
    }
    return res;
}

vector<int> rabin_karp(const string &s, const string &t) {
    const int P = 53;
    const int MOD = 1e9 + 7;

    int n = (int)s.size();
    int m = (int)t.size();

    vector<int> pw(m), inv(m);
    pw[0] = 1;
    for (int i = 1; i < m; ++i)  {
        pw[i] = Mul(pw[i - 1], P, MOD);
        inv[i] = binpow(pw[i], MOD - 2, MOD);
    }

    int h_s = 0;
    vector<int> h_t(m);
    for (int i = 0; i < m; ++i) {
        if (i < n) {
            h_s = Add(h_s, Mul(s[i] - 'A' + 1, pw[i], MOD), MOD);
        }
        if (i == 0) {
            h_t[i] = Mul(t[i] - 'A' + 1, pw[0], MOD);
            continue;
        }
        h_t[i] = Add(h_t[i - 1], Mul(t[i] - 'A' + 1, pw[i], MOD), MOD);
    }
    vector<int> ans;
    for (int i = 0; i < m - n + 1; ++i) {
        int curr_hash = h_t[i + n - 1];
        if (i > 0) {
            int inv_hash = inv[i];
            curr_hash = Mul(Sub(curr_hash, h_t[i - 1], MOD), inv_hash, MOD);
        }
        if (curr_hash == h_s) {
            ans.push_back(i);
        }
        if ((int)ans.size() == 1e3) break;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout)

    string s, t;
    cin >> s >> t;
    if ((int)s.size() > (int)t.size()) {
        cout << "0\n";
        return 0;
    } 
    vector<int> ans = rabin_karp(s, t);
    cout << (int)ans.size() << "\n";
    for (int &x : ans) cout << x << ' ';
    return 0;
}