Cod sursa(job #2767801)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 7 august 2021 18:53:27
Problema Abc2 Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MOD 100009
#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<long long> set[MOD];
long long hashFactor = 1;

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

void addWord(string s) {
	long long hashVal = 0;
	for (int i =  0; i < len_s2; i++) {
		hashVal = hashVal * HASH + (s[i] - 'a');
	}
	if (!setContains(hashVal))
		set[hashVal % MOD].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);
	}
	
	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 = (hashVal - (prevVal * hashFactor)) * HASH + val;
		if (setContains(hashVal))
			count++;
	}
	g << count;
	return 0;
}