Cod sursa(job #2295870)

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

using namespace std;

const int kBase = 28;

vector<int64_t> Compute(string s) {
    int n = s.size();
    vector<int64_t> ret(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        ret[i + 1] = 1LL * ret[i] * kBase + s[i];
    }
    return ret;
}

int main() {
    ifstream cin("abc2.in");
    ofstream cout("abc2.out");
    unordered_set<int64_t> pats;
    
    string s; cin >> s;
    int l = -1;
    
    string p;
    while (cin >> p) {
        l = p.size();
        pats.insert(Compute(p).back());
    }
    
    vector<int64_t> has = Compute(s);
    int64_t ans = 0;
    
    vector<int64_t> pw(l + 1, 0);
    pw[0] = 1;
    for (int i = 1; i <= l; ++i) {
        pw[i] = pw[i - 1] * kBase;
    }
    
    for (int i = l; i < has.size(); ++i) {
        int64_t now = has[i] - 1LL * has[i - l] * pw[l];
        ans += pats.count(now);
    }
    cout << ans << endl;
    
    return 0;
}