Pagini recente » Cod sursa (job #2437279) | Cod sursa (job #2824754) | Cod sursa (job #1745520) | Cod sursa (job #1267655) | Cod sursa (job #2294748)
#include <stdio.h>
#include <vector>
#include <string.h>
#include <math.h>
using namespace std;
char text[10000002];
int nr_cuv, lung_cuv, lung_text;
long long int sol, cod_cuvant_curent, expo = 1ll;
vector <long long 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(long long int val) {
int cod = val % 10003;
for (int i = 0; i < hashh[cod].size(); i++)
if (hashh[cod][i] == val)
return 1;
return 0;
}
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;
}
long long int conversie, exp;
int cod;
lung_cuv = strlen(cuvinte[0]);
// fara proceduri sa intre in timp
conversie = 0;
exp = 1;
for (int i = 0; i < lung_cuv; i++) {
conversie += exp * (cuvinte[nr_cuv][i] - 'a');
exp *= 3;
}
cod = conversie % 10003;
hashh[cod].push_back(conversie);
//
nr_cuv++;
while (scanf("%s", &cuvinte[nr_cuv]) == 1) {
conversie = 0;
exp = 1;
for (int i = 0; i < lung_cuv; i++) {
conversie += exp * (cuvinte[nr_cuv][i] - 'a');
exp *= 3;
}
cod = conversie % 10003;
if (!cauta(conversie))
hashh[cod].push_back(conversie);
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++;
long long 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;
}