Cod sursa(job #2588825)

Utilizator minecraft3Vintila Valentin Ioan minecraft3 Data 25 martie 2020 15:18:57
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

char s[10000005], cuv[25]; //TODO: *10
LL v[50005], vi, rez, p;
int i, size_cuv;

bool verify(LL x) {
    return (*lower_bound(v, v+vi, x) == x);
}

LL pow_LL(LL x, LL y) {
    if(y == 0) return 1;
    if(y % 2ll == 0) return pow_LL(x * x, y / 2);
    return x * pow_LL(x * x, y / 2);
}

int main() {
    ifstream fin("abc2.in");
    ofstream fout("abc2.out");

    fin >> s;
    while(fin >> cuv) {
        for(i = 0; cuv[i]; ++i)
            v[vi] = v[vi] * 3ll + (LL)(cuv[i] - 'a');
        ++vi; size_cuv = i;
    }
    sort(v, v+vi);
    p = pow_LL(3, size_cuv-1);

    LL cur = 0;
    for(i = 0; i < size_cuv; ++i)
        cur = cur * 3ll + (LL)(s[i] - 'a');
    rez += verify(cur);
    for(; s[i]; ++i) {
        cur = (cur - p * (LL)(s[i-size_cuv]-'a')) * 3ll + (LL)(s[i] - 'a');
        rez += verify(cur);
    }

    fout << rez;
    fin.close(); fout.close();
    return 0;
}