Cod sursa(job #2099783)

Utilizator MaligMamaliga cu smantana Malig Data 4 ianuarie 2018 17:55:58
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
#define pb push_back
#define mp make_pair
const ll NMax = 5e4 + 5;
const ll inf = 1e9 + 5;
const ll mod = 100000001;
const ll base = 73;
using zint = int;

ll N,M;
string str,cuv;

int main() {
    in>>(str);
    M = str.size();

    in>>cuv;
    int len;
    unordered_set<ll> vis;
    while (!in.fail()) {
        len = cuv.size();

        ll digest = 0;
        for (int k=0;k < len;++k) {
            digest = (digest * base + cuv[k] * base) % mod;
        }

        vis.insert(digest);

        in>>cuv;
    }

    ll strDigest = 0,pw = 1;
    for (int k=0;k < len;++k) {
        strDigest = (strDigest * base + str[k] * base) % mod;

        pw = (pw * base) % mod;
    }

    ll ans = 0;
    if (vis.find(strDigest) != vis.end()) {
        ++ans;
        //pv(ans);
    }

    for (int j=len;j < M;++j) {
        strDigest = ((strDigest - ((pw * str[j-len]) % mod) + mod) * base + str[j] * base) % mod;

        if (vis.find(strDigest) != vis.end()) {
            ++ans;
        }
    }

    out<<ans<<'\n';

    in.close();out.close();
    return 0;
}