Cod sursa(job #1857667)

Utilizator greenadexIulia Harasim greenadex Data 26 ianuarie 2017 15:30:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
 
using namespace std;
 
const string name = "abc2",
             in_file = name + ".in",
             out_file = name + ".out";
 
ifstream fin(in_file);
ofstream fout(out_file);
 
const int MOD = 1e5 + 3;
vector<unsigned> hash_table[MOD];
string str;
unsigned length_word;
unsigned power3[21];

int hash_function(unsigned number) {
	return number % MOD;
}

void add(unsigned key) {
	int vaca = hash_function(key);
	for (unsigned number : hash_table[vaca]) {
		if (number == key) {
			return;
		}
	}
	hash_table[vaca].pb(key);
}

bool contains(unsigned key) {
	int vaca = hash_function(key);
	for (unsigned number : hash_table[vaca]) {
		if (number == key) {
			return true;
		}
	}
	return false;
}

unsigned add_letter(unsigned nr, unsigned digit) {
//	unsigned temp = nr / power3[length_word - 1];
	unsigned temp = 1;
	nr -= temp * power3[length_word - 1];
	nr *= 3;
	nr += digit;
	return nr;
}

void process_word(string& word) {
	unsigned current_number = 0;
	for (unsigned i = 0; i < length_word; i++) {
		current_number = add_letter(current_number, word[i] - 'a');
	}
	add(current_number);
}

int main() {
	fin >> str;
	
	power3[0] = 1;
	for (int i = 1; i <= 20; i++) {
		power3[i] = 3 * power3[i - 1]; 
	}

	string word;
	while (fin >> word) {
		if (!length_word) {
			length_word = word.size();
			if (length_word > str.size()) {
				fout << 0;
				return 0;
			}
		}
		process_word(word);
	}	

	int sol = 0;
	unsigned current_number = 0;
	for (unsigned i = 0; i < str.size(); i++) {
		current_number = add_letter(current_number, str[i] - 'a');
		if (length_word <= i + 1) {
			if (contains(current_number)) {
				sol++;
			}
		}
	}
	
	fout << sol;
	return 0;
}