Cod sursa(job #2099794)

Utilizator MaligMamaliga cu smantana Malig Data 4 ianuarie 2018 18:00:49
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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 = 1e7 + 5;
const ll inf = 1e9 + 5;
const ll mod = 100000001;
const ull base = 73;
using zint = int;

ll N,M;
char str[NMax];

int main() {
    in>>(str);
    M = strlen(str);

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

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

        vis.insert(digest);

        in>>cuv;
    }

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

        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]) * base + str[j] * base;

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

    out<<ans<<'\n';

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