Pagini recente » Cod sursa (job #2666368) | Cod sursa (job #690604) | Cod sursa (job #150481) | Cod sursa (job #2396533) | Cod sursa (job #2294678)
#include <stdio.h>
#include <vector>
#include <string>
#include <string.h>
using namespace std;
char text[10000002];
int nr_cuv, lung_cuv, lung_text;
vector <string> hashh[735337];
// 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
int h(char const cuvant[22]) {
long long int conversie = 0, exp = 1;
for (int i = 0; i < lung_cuv; i++) {
conversie += exp * cuvant[i] - 'a';
exp *= 3;
}
return conversie % 735337;
}
int cauta(char const cuvant[22]) {
int cod = h(cuvant);
for (int i = 0; i < hashh[cod].size(); i++)
if (strcmp(hashh[cod][i].c_str(), cuvant) == 0)
return i;
return -1;
}
void insereaza(char cuvant[22]) {
int cod = h(cuvant);
if (cauta(cuvant) == -1)
hashh[cod].push_back(cuvant);
}
int main() {
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
char cuvinte[50000][22];
long long int sol = 0;
fgets(text, 10000002, stdin);
lung_text = strlen(text);
if (!scanf("%s", cuvinte[nr_cuv])) {
printf("0");
return 0;
}
lung_cuv = strlen(cuvinte[0]);
insereaza(cuvinte[nr_cuv]);
nr_cuv++;
while (scanf("%s", &cuvinte[nr_cuv]) == 1) {
insereaza(cuvinte[nr_cuv]);
nr_cuv++;
}
string t(text);
string cuv = t.substr(0, lung_cuv);
if (cauta(cuv.c_str()) != -1)
sol++;
for (int i = 1; i < lung_text - lung_cuv; i++) {
cuv.erase(0, 1);
cuv.push_back(text[i + lung_cuv - 1]);
if (cauta(cuv.c_str()) != -1)
sol++;
}
printf("%lld", sol);
return 0;
}