Cod sursa(job #2295876)

Utilizator mirunazMiruna Zavelca mirunaz Data 3 decembrie 2018 23:53:26
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 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;
}

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

    vector<int64_t> pats;    
    string s; cin >> s;
    int l = -1;
    
    string p;
    while (cin >> p) {
        l = p.size();
        pats.push_back(Compute(p));
    }
    
    sort(pats.begin(), pats.end());
    pats.erase(unique(pats.begin(), pats.end()), pats.end());
    
    int64_t 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 += binary_search(pats.begin(), pats.end(), has);
            has -= pw * s[i - l + 1];
        }
    }
    cout << ans << endl;
    
    return 0;
}