Cod sursa(job #2295905)

Utilizator mirunazMiruna Zavelca mirunaz Data 4 decembrie 2018 00:23:21
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

const int kBase = 28;

int64_t Compute(const string& s) {
    int n = s.size(); int64_t ret = 0;
    for (int i = 0; i < n; ++i) {
        ret = ret * kBase + s[i];
    }
    return ret;
}

const int kMod = 666013;
vector<int64_t> has[kMod];

void Insert(int64_t val) {
    auto idx = val % kMod;
    if (idx < 0) idx += kMod;
    auto& v = has[idx];
    if (count(v.begin(), v.end(), val)) return;
    v.push_back(val);
}

bool Get(int64_t val) {
    auto idx = val % kMod;
    if (idx < 0) idx += kMod;
    auto& v = has[idx];
    return count(v.begin(), v.end(), val);
}

int main() {
    //ifstream cin("abc2.in");
    //ofstream cout("abc2.out");

    string s; cin >> s;
    int l = -1;
    
    string p;
    while (cin >> p) {
        l = p.size();
        Insert(Compute(p));
    }
    
    int ans = 0;
    
    int64_t pw = 1;
    for (int i = 1; i < l; ++i)
        pw = pw * kBase;
    
    int64_t has = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        has = has * kBase + s[i];
        if (i + 1 >= l) {
            ans += Get(has);
            has -= pw * s[i - l + 1];
        }
    }
    cout << ans << endl;
    
    return 0;
}