Cod sursa(job #2443233)

Utilizator cory1211Corina cory1211 Data 26 iulie 2019 23:55:13
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
#include <string.h>
#include <fstream>
#include <iostream>
#define mod 29989

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;
	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';
		}
		Hash[Hash_value % mod].push_back(Hash_value);
	}

	for(int i = 0; i < len; i++) {
		pwr = 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;
}