Cod sursa(job #2099771)

Utilizator MaligMamaliga cu smantana Malig Data 4 ianuarie 2018 17:44:31
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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;
string v[NMax];

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

    unordered_set<string> st;
    in>>cuv;
    while (!in.fail()) {
        auto p = st.insert(cuv);

        if (p.second) {
            v[++N] = cuv;
        }

        in>>cuv;
    }

    ll strDigest1 = 0;
    ll len = v[1].size(),pw1 = 1;
    unordered_set<int> vis;
    for (int i=1;i <= N;++i) {

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

        vis.insert(digest);
    }


    for (int k=0;k < len;++k) {
        strDigest1 = (strDigest1 * base + str[k] * base) % mod;

        pw1 = (pw1 * base) % mod;
    }

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

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

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

    out<<ans<<'\n';

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