Cod sursa(job #2588836)

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

using namespace std;

typedef long long LL;

#define K 666019
#define N 50005
#define M 100000 /*TODO: */

char s[M], cuv[25];
LL val[N], urm[N], lst[K], nr, vi, rez, p, cur;
int i, size_cuv;

void add(int x) {
    val[++nr] = x;
    urm[nr] = lst[x%K];
    lst[x%K] = nr;
}

bool verify(LL x) {
    for(int j = lst[x%K]; j; j = urm[j])
        if(val[j] == x) return true;
    return false;
}

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 = cur = 0; cuv[i]; ++i)
            cur = cur * 3ll + (LL)(cuv[i] - 'a');
        add(cur); size_cuv = i;
    }
    p = pow_LL(3, size_cuv-1);

    for(i = cur = 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;
}