Pagini recente » Cod sursa (job #3126730) | Cod sursa (job #2921560) | Cod sursa (job #3214984) | Cod sursa (job #2429340) | Cod sursa (job #2650624)
#include<iostream>
#include<string>
#include<stdlib.h>
#include<fstream>
#include<vector>
#define M 666019
#include<cmath>
using namespace std;
ifstream f ("abc2.in");
ofstream g ("abc2.out");
const int cuvmax = 5e4 + 1;
unsigned int number;
//toate sirurile sunt initializate cu 0
unsigned int lista[M] ,val[cuvmax], urm[cuvmax];
//x-ul primit este cuvantul trecut prin functia de hash
bool belongs(unsigned int x){
int i;
int c = x % M;
for(i = lista[c]; i != 0; i = urm[i])
if(val[i] == x)
return true;
return false;
}
void add(unsigned int x){
//folosesc mod pentru a adauga in tabela
int c = x % M;
//verific daca exista deja
if(belongs(x))
return;
val[++number] = x;//val va tine valoarea hash a cuvantului
urm[number] = lista[c]; //urm retine indicele noii valori in
//in cazul unie posibile coliziuni
lista[c] = number;//lista tine minte indicii pe care se afla
// valorile hash_uite
}
//deoarece cuvintele primite au doar 3 litere diferite in comp
//le transform in numere in baza 3
unsigned int hash_fun(string str){
unsigned int c = 0, i;
for(i = 0; i <str.length(); i++)
c = c*3 + (str[i] - 'a');
return c;
}
int main(){
string str, word;
unsigned int i,ln;
f >> str;
while(f>>word)
add(hash_fun(word));
ln = word.length();
unsigned int r = 0;
unsigned int c = hash_fun(str.substr(0,ln));
if(belongs(c))
r++;
int p3 = pow(3,ln-1);
for(i = ln; i < str.length(); i++){
c = (c - p3*(str[i-ln] -'a')) * 3 + (str[i]-'a');
if(belongs(c))
r++;
}
g<<r;
return 0;
}