Cod sursa(job #2470322)

Utilizator mirceatlxhaha haha mirceatlx Data 8 octombrie 2019 23:52:38
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include <string.h>
#include <fstream>
#include <iostream>
#define mod 5099
 
using namespace std;
 
ifstream f("abc2.in");
ofstream g("abc2.out");
 
char s[10000005], c[25];
vector <unsigned int> Hash[mod];
 
int search(unsigned int val) {
	int index = val % mod;
	for(auto i : Hash[index]) {
		if(i == val) return 1;
	}
	/*vector<unsigned int> v = Hash[index];
	int len = v.size();
	for(int i = 0; i < len; i++) {
		if(v[i] == val)
			return 1;
    }*/
 
	return 0;
}
 
int main() {
	f >> s;
	int len, nr = 0;
	unsigned int pwr = 1;
	unsigned int Hash_value;
 
	while(f >> c) {
		len = strlen(c);
		Hash_value = 0;
		for(int i = 0; i < len; i++) {
			Hash_value = Hash_value * 3 + c[i] - 'a';
		}
 
		int idx = Hash_value % mod;
		for(auto i : Hash[idx]) {
			if(i == Hash_value)
				continue;
		}
		Hash[Hash_value % mod].push_back(Hash_value);
	}
 
	for(int i = 0; i < len; i++) {
		pwr *= 3;
	}
 
	int len_txt = strlen(s);
	Hash_value = 0;
	for(int i = 0; i < len_txt; i++) {
		Hash_value = Hash_value * 3  + (s[i] - 'a');
 
		if(i >= len) {
			Hash_value = Hash_value - pwr * (s[i - len] - 'a');
		}
 
		if(i >= len - 1) {
			nr += search(Hash_value);
		}
	}
 
	g << nr;
	return 0;
}