Cod sursa(job #2771719)

Utilizator nubnubMeh Neh nubnub Data 28 august 2021 20:15:51
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb

#include <stdio.h>
#include <vector>
#include <string.h>
#include <math.h>

using namespace std;

char text[10000002];
int nr_cuv, lung_cuv, lung_text;
unsigned int sol, cod_cuvant_curent, expo = 1ll;
vector <unsigned int> hashh[10003];
// codificam numerele in baza 3(deoarece cuvintele se formeaza doar cu a, b si c), deci sunt maxim 3^20 - 1 = 3 486 784 400 cazuri posibile, deci va trebui sa facem un hash modulo

inline bool cauta(unsigned int val) {
    int cod = val % 10003;
    for (int i = 0; i < hashh[cod].size(); i++)
        if (hashh[cod][i] == val)
            return 1;
    return 0;
}

inline int h(char const cuvant[22]) {
    unsigned int conversie = 0, exp = 1;
    for (int i = 0; i < lung_cuv; i++) {
        conversie += exp * (cuvant[i] - 'a');
        exp *= 3;
    }
    int cod = conversie % 10003;
    if (!cauta(conversie))
        hashh[cod].push_back(conversie);
}

int main() {
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);
	char cuvinte[50000][22];
	fgets(text, 10000002, stdin);
	lung_text = strlen(text);
	if (!scanf("%s", &cuvinte[nr_cuv])) {
        printf("0");
        return 0;
	}
	lung_cuv = strlen(cuvinte[0]);
	h(cuvinte[nr_cuv]);
	nr_cuv++;
	while (scanf("%s", &cuvinte[nr_cuv]) == 1) {
        h(cuvinte[nr_cuv]);
        nr_cuv++;
	}
    for (int i = 0; i < lung_cuv; i++) {
        cod_cuvant_curent += expo * (text[i] - 'a');
        expo *= 3;
    }
    if (cauta(cod_cuvant_curent))
        sol++;
    unsigned int putere = pow(3, lung_cuv - 1);
    for (int i = 1; i < lung_text - lung_cuv; i++) {
        // cele 2 operatii sunt echivalente cu a scoate prima litera dintr-un cuvant si a o adauga una noua ca ultima litera
        cod_cuvant_curent /= 3;
        cod_cuvant_curent += putere * (text[i + lung_cuv - 1] - 'a');
        if (cauta(cod_cuvant_curent))
            sol++;
    }
    printf("%lld", sol);
	return 0;
}