Cod sursa(job #2767796)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 7 august 2021 18:38:08
Problema Abc2 Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MOD 10009
#define HASH 3
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
int len_s1, len_s2, count = 0;
string s1, s2;
vector<unsigned long long> set[MOD];
unsigned long long hashFactor = 1;

bool setContains(unsigned long long hashVal) {
	unsigned long long pos = 1ULL * hashVal % MOD;
	for (int i = 0; i < set[pos].size(); i++) {
		if (set[pos][i] == hashVal) {
			return true;
		}
	}
	return false;
}

void addWord(string s) {
	unsigned long long hashVal = 0;
	for (int i =  0; i < len_s2; i++) {
		hashVal = hashVal * HASH + (s[i] - 'a');
	}
	//cout << s << " " << hashVal << "\n";
	if (!setContains(hashVal))
		set[hashVal % MOD].push_back(hashVal);
}
void Push(unsigned long long hashVal){
    if(!setContains(hashVal)) {
        unsigned long long pos = 1ULL * hashVal % MOD;
        set[pos].push_back(hashVal);
    }
}
int main() {
	f >> s1;
	f >> s2;
	len_s1 = s1.length();
	len_s2 = s2.length();
	addWord(s2);
	
	for (int i = 1; i < len_s2; i++) {
		hashFactor = hashFactor * HASH;
	}
	
	while (f >> s2) {
		addWord(s2);
	}
	unsigned long long hashVal = 0;
	for (int i = 0; i < len_s2; i++) {
		hashVal = hashVal * HASH + (s1[i] - 'a');
	}
	if (setContains(hashVal))
		count++;
		
	for (int i = len_s2; i < len_s1; i++) {
		int prevVal = s1[i-len_s2] - 'a', val = s1[i] - 'a';
		hashVal = (1ULL * hashVal - (1ULL * prevVal * hashFactor));
		hashVal = 1ULL * hashVal * HASH + val;
		if (setContains(hashVal))
			count++;
	}
	
	g << count;
	return 0;
}