Cod sursa(job #2297392)

Utilizator flibiaVisanu Cristian flibia Data 5 decembrie 2018 19:46:57
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
// NU VA APUCATI DE CACATU ASTA DE PROBLEMA
#include <bits/stdc++.h>
#pragma GCC optimize("03")
#define MOD 29317
#define ll long long

using namespace std;

ifstream in("abc2.in");
ofstream out("abc2.out");

char s[10000100], g[50100];
int sz, gz, ans;
ll pw[30];
vector <ll> v[MOD];

bool get(ll key) {
	for (auto i : v[key % MOD])
		if (i == key)
			return 1;
	return 0;
}

int main() {
	pw[0] = 1;
	for (int i = 1; i <= 21; i++) 
		pw[i] = 3LL * pw[i - 1];
	in >> s;
	while (in >> g) {
		gz = strlen(g);
		ll hsh = 0;
		for (int i = 0; i < gz; i++)
			hsh = 3LL * hsh + g[i] - 48;
		if (!get(hsh))
			v[hsh % MOD].push_back(hsh);
	}
	sz = strlen(s);
	ll hsh = 0;;
	for (int i = 0; i < gz; i++) {
		hsh = 3LL * hsh + s[i] - 48;
	}
	ans += get(hsh);
	for (int i = gz; i < sz; i++) {
		hsh = 3LL * hsh - pw[gz] * (s[i - gz] - 48) + s[i] - 48;
		ans += get(hsh);
	}
	out << ans;
	return 0;
}