Cod sursa(job #2967003)

Utilizator MR0L3eXMaracine Constantin Razvan MR0L3eX Data 18 ianuarie 2023 21:09:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include "bits/stdc++.h"
#include <cstdio>

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 MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int B1 = 53;
const int B2 = 59;
const int mxN = 2e6;

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

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

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

int pw1[mxN], pw2[mxN];

pair<int, int> get_hash(const string &s) {
    int h1 = 0, h2 = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        h1 = add(mul(h1, B1, MOD1), s[i], MOD1); 
        h2 = add(mul(h2, B2, MOD2), s[i], MOD2); 
    }
    return {h1, h2};
}

int txt_h1[mxN + 1], txt_h2[mxN + 1];
void compute_hash(const string &s) {
    for (int i = 0; i < (int)s.size(); ++i) {
        txt_h1[i + 1] = add(mul(txt_h1[i], B1, MOD1), s[i], MOD1);
        txt_h2[i + 1] = add(mul(txt_h2[i], B2, MOD2), s[i], MOD2);
    }
}

pair<int, int> qry(const int &l, const int &r) {
    pair<int, int> ans;
    ans.first = sub(txt_h1[r], mul(txt_h1[l], pw1[r - l], MOD1), MOD1);
    ans.second = sub(txt_h2[r], mul(txt_h2[l], pw2[r - l], MOD2), MOD2);
    return ans;
}

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

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

    pw1[0] = pw2[0] = 1;
    for (int i = 1; i < mxN; ++i) {
        pw1[i] = mul(pw1[i - 1], B1, MOD1);
        pw2[i] = mul(pw2[i - 1], B2, MOD2);
    }

    string text, pattern;
    cin >> pattern >> text;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m > n ) {
        cout << "0\n";
        return 0;
    }
    int ans = 0;
    vector<int> poz;
    compute_hash(text);
    pair<int, int> patt_h = get_hash(pattern);
    for (int i = 0; i <= n - m; ++i) {
        pair<int, int> curr_h = qry(i, i + m);
        if (curr_h == patt_h) {
            if (ans < 1e3) poz.push_back(i);
            ans++;

        }
    }
    cout << ans << "\n";
    for (int &x : poz) cout << x << " ";
    cout << "\n";
    return 0;
}