Pagini recente » Cod sursa (job #1186390) | Cod sursa (job #780028) | Cod sursa (job #1946690) | Cod sursa (job #268084) | Cod sursa (job #2293364)
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
char text_makako[10000005];
ifstream f("abc2.in");
ofstream g("abc2.out");
char cuvant[23];
vector<int>hash_table[35678];
void adauga_in_hash(int x)
{
int poz = x % 35678;
hash_table[poz].push_back(x);
}
int verifica(int x) {
int pozitie = x % 35678;
int ok = 0;
for(int i = 0; i<hash_table[pozitie].size(); i++)
if(hash_table[pozitie][i] == x) ok = 1;
return ok;
}
int main() {
int lungime_sir, lungime_cuvant;
int solutie = 0;
int p = 1;
int aux;
int hash_curent = 0;
f>>text_makako;
lungime_sir = strlen(text_makako);
while (f >> cuvant)
{
lungime_cuvant = strlen(cuvant);
int k = 0;
//pentru fiecare cuvant, genereaza un hash
for (int i = 0; i < lungime_cuvant; i++)
//codez fiecare cuvant si ii creez in hash o legatura
k = k * 3 + (cuvant[i] - 'a');
adauga_in_hash(k);
}
aux = lungime_cuvant;
while (aux > 1)
{
p = p * 3;
aux--;
}
for(int i = 0; i< lungime_cuvant; i++)
//fac un caz separat pt primul "cuvant", creez hashul si il caut
hash_curent = hash_curent * 3 + text_makako[i] - 'a';
if(verifica(hash_curent) != 0)
solutie ++;
//pentru fiecare litera in parte parcurg sirul
for( int i = lungime_cuvant; i < lungime_sir; i++)
{
//si elimin de fiecare data prima litera din fostul cuvant
hash_curent = hash_curent - (text_makako[i - lungime_cuvant] - 'a') * p;
//noua litera venita e adaugata in hash(creez un nou cod)
hash_curent = hash_curent * 3 + text_makako[i] - 'a';
if(verifica(hash_curent) != 0)
solutie ++;
}
g << solutie;
return 0;
}