Cod sursa(job #2295856)

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

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

const int MOD1 = 666013, MOD2 = 1 << 25, B = 250;
    
using i64 = long long;
using pii = pair<int, int>;

struct MUIE_TAMIO {
    vector<int> hsh[MOD1];

    void insert(int h1, int h2) {
        hsh[h1].push_back(h2);
    }

    bool find(int h1, int h2) {
        for (auto i: hsh[h1])
            if (i == h2)
                return true;
            return false;
    }
};

MUIE_TAMIO 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) {
        auto tmp = get_hsh(str);
        s.insert(tmp.first, tmp.second);
        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(h1, h2));

    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(h1, h2))
            antwoord+= 1;
    }

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

    return 0;
}

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