Cod sursa(job #2811753)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 3 decembrie 2021 07:38:19
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MOD 30007
#define HASH 3
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
int lenS1, lenS2, count = 0;
string s1, s2;
vector<unsigned int> set[MOD];
unsigned int hashFactor = 1;

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

void addWord(string s) {
	unsigned int hashVal = 0;
	for (int i =  0; i < lenS2; i++) {
		hashVal = hashVal * HASH + (s[i] - 'a');
	}
	if (!setContains(hashVal)) {
		unsigned int key = hashVal % MOD;
		set[key].push_back(hashVal);
	}
}

int main() {
	f >> s1;
	lenS1 = s1.length();
	while (f >> s2) {
		lenS2 = s2.length();
		addWord(s2);
	}

	for (int i = 1; i < lenS2; i++) {
		hashFactor = hashFactor * HASH;
	}

	unsigned int hashVal = 0;
	for (int i = 0; i < lenS2; i++) {
		hashVal = hashVal * HASH + (s1[i] - 'a');
	}
	if (setContains(hashVal)) {
		count++;
	}

	for (int i = lenS2; i < lenS1; i++) {
		int prevVal = s1[i-lenS2] - 'a', val = s1[i] - 'a';
		hashVal = (hashVal - (prevVal * hashFactor)) * HASH + val;
		if (setContains(hashVal))
			count++;
	}
	g << count;
	return 0;
}