Cod sursa(job #2768681)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 11 august 2021 19:34:10
Problema Abc2 Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MOD 10003
#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;
	len_s1 = s1.length();
	while (f >> s2) {
		len_s2 = s2.length();
		addWord(s2);
	}
	
	for (int i = 1; i < len_s2; i++) {
		hashFactor = hashFactor * HASH;
	}
	
	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;
}