Cod sursa(job #2650624)

Utilizator Rmrn56Maracine Mihail Robert Rmrn56 Data 19 septembrie 2020 15:38:09
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#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;
}