Cod sursa(job #2295848)

Utilizator mirunazMiruna Zavelca mirunaz Data 3 decembrie 2018 23:26:57
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("abc2.in");
ofstream fo("abc2.out");

const int MOD1 = 666013, MOD2 = 1e9 + 7, B = 250;

using i64 = long long;
using pii = pair<int, int>;

set<pii> s;
string vsb, str;
int antwoord, len, n;

static pii get_hsh(const string &str) {
    i64 h1 = 0, h2 = 0;
    for (auto i: str) {
        h1 = (h1 * B + i) % MOD1;
        h2 = (h2 * B + i) % MOD2;
    }
    return pii(h1, h2);
}

static void fix(i64 &x, i64 &y) {
    if (x < 0)
        x+= MOD1;
    if (y < 0)
        y+= MOD2;
}

int main(){
    i64 h1 = 0, h2 = 0, pwr1 = 1, pwr2 = 1;

    fi >> vsb;
    n = vsb.size();
    while (fi >> str) {
        s.insert(get_hsh(str));
        len = str.size();
    }

    for (int i = 0; i < len; ++i) {
        h1 = (h1 * B + vsb[i]) % MOD1;
        h2 = (h2 * B + vsb[i]) % MOD2;
        if (i + 1 == len)
            break;
        pwr1 = pwr1 * B % MOD1;
        pwr2 = pwr2 * B % MOD2;
    }
    antwoord+= int(s.find(pii(h1, h2)) != end(s));

    for (int i = 0; i + len < n; ++i) {
        h1 = (h1 - pwr1 * vsb[i]) % MOD1;
        h2 = (h2 - pwr2 * vsb[i]) % MOD2;
        fix(h1, h2);
        h1 = (h1 * B + vsb[i + len]) % MOD1;
        h2 = (h2 * B + vsb[i + len]) % MOD2;
        if (s.find(pii(h1, h2)) != end(s))
            antwoord+= 1;
    }

    fo << antwoord << endl;
    cerr << antwoord << endl;

    return 0;
}

/* Prostitutia
 * nu este o recompensa adecvata codatului byat proola
 */