Cod sursa(job #2767776)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 7 august 2021 18:24:18
Problema Abc2 Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.6 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) {
	int 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);
}
int main() {
	f >> s1;
	len_s1 = s1.length();
	f >> s2;
	len_s2 = s2.length();
	addWord(s2);
	
	for (int i = 1; i < len_s2; i++) {
		hashFactor = hashFactor * HASH;
	}
	
	while (cin >> s2) {
		addWord(s2);
	}
	//cout << "\n";
	unsigned long long hashVal = 0;
	for (int i = 0; i < len_s2; i++) {
		hashVal = hashVal * HASH + (s1[i] - 'a');
	}
	//cout << len_s2 << " " << hashVal << "\n";
	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;
		
		//cod = 1ULL * cod - p * 1ULL * (s1[i - M] - 'a' )   ;
        //cod = 1ULL * cod * 3 + (s1[i] - 'a');
		if (setContains(hashVal))
			count++;
		//cout << i << " " << hashVal << "\n";
	}
	
	g << count;
	return 0;
}