Cod sursa(job #2767766)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 7 august 2021 18:08:07
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 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<long long> set[MOD];
long long hashFactor = 1;
bool setContains(long long hashVal) {
	int 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' + 1);
	}
	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);
	}
	
	long long hashVal = 0;
	for (int i = 0; i < len_s2; i++) {
		hashVal = hashVal * HASH + (s1[i] - 'a' + 1);
	}
	
	if (setContains(hashVal))
		count++;
	for (int i = len_s2; i < len_s1; i++) {
		int prevVal = s1[i-len_s2] - 'a' + 1, val = s1[i] - 'a' + 1;
		hashVal = (hashVal - (prevVal * hashFactor)) * HASH + val;
		if (setContains(hashVal))
			count++;
	}
	
	g << count;
	return 0;
}