Cod sursa(job #2869922)

Utilizator MR0L3eXMaracine Constantin Razvan MR0L3eX Data 11 martie 2022 22:17:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.77 kb
#include "bits/stdc++.h"

using namespace std;

using ld = long double;
using ll = long long;
using ull = unsigned long long;
using db = double;

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

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

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)))

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

void setIO(string name = "") {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
	if (sz(name)) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

const ld PI = acos((ld)-1);
const int d4i[4] = {-1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int INF = 1e9;
const int mxN = 2e5;
const char nl = '\n';
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
int B = 73;

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

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;
}

void solve() {
    string patt, txt;
    cin >> patt >> txt;

    if (sz(patt) > sz(txt)) {
        cout << "0\n";
        return;
    }

    pair<int, int> hash_patt = {0, 0}, MOD = {MOD1, MOD2}, PW = {1, 1};
    for (int i = 0; i < sz(patt); ++i) {
        hash_patt.fi = Add(Mul(hash_patt.fi, B, MOD.fi), patt[i], MOD.fi);
        hash_patt.se = Add(Mul(hash_patt.se, B, MOD.se), patt[i], MOD.se);

        if (i) {
            PW.fi = Mul(PW.fi, B, MOD.fi);
            PW.se = Mul(PW.se, B, MOD.se);
        }
    }

    pair<int, int> hash_txt = {0 , 0};
    for (int i = 0; i < sz(patt); ++i) {
        hash_txt.fi = Add(Mul(hash_txt.fi, B, MOD.fi), txt[i], MOD.fi);
        hash_txt.se = Add(Mul(hash_txt.se, B, MOD.se), txt[i], MOD.se);
    }

    int ans = 0;
    vector<int> res;
    if (hash_txt == hash_patt) {
        res.pb(0);
        ++ans;
    }

    for (int i = sz(patt); i < sz(txt); ++i) {

        hash_txt.fi = Add(Mul(Sub(hash_txt.fi, Mul(txt[i - sz(patt)], PW.fi, MOD.fi), MOD.fi), B, MOD.fi), txt[i], MOD.fi);
        hash_txt.se = Add(Mul(Sub(hash_txt.se, Mul(txt[i - sz(patt)], PW.se, MOD.se), MOD.se), B, MOD.se), txt[i], MOD.se);
        //hash_txt.fi = ((hash_txt.fi - (txt[i - sz(patt)] * PW.fi) % MOD.fi + MOD.fi) * B + txt[i]) % MOD.fi;
        //hash_txt.se = ((hash_txt.se - (txt[i - sz(patt)] * PW.se) % MOD.se + MOD.se) * B + txt[i]) % MOD.se;

        if (hash_txt == hash_patt) {
            if (ans < 1e3) res.pb(i - sz(patt) + 1);
            ++ans;
        }
    }

    cout << ans << nl;
    for (int &x : res) {
        cout << x << ' ';
    }
    cout << nl;
}

int main() {
    setIO("strmatch");

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}