Cod sursa(job #2297360)

Utilizator flibiaVisanu Cristian flibia Data 5 decembrie 2018 19:07:12
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
#define MOD1 104053  
#define MOD2 104059

using namespace std;

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

char s[10000100], g[50100];
int sz, gz, pw[30], ans;
vector <int> v[MOD2 + 123];

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

void baga(int key) {
	if (!get(key))
		v[key % MOD2].push_back(key);
}

int main() {
	pw[0] = 1;
	for (int i = 1; i <= 21; i++)
		pw[i] = (pw[i - 1] * 31) % MOD1;
	in >> s;
	while (in >> g) {
		gz = strlen(g);
		int hsh = 0;
		for (int i = 0; i < gz; i++)
			hsh = (hsh + (int) g[i] * pw[gz - i - 1]) % MOD1;
		baga(hsh);
	}
	sz = strlen(s);
	int hsh = 0;
	for (int i = 0; i < gz; i++)
		hsh = (hsh + (int) s[i] * pw[gz - i - 1]) % MOD1;
	baga(hsh);
	ans += get(hsh);
	for (int i = gz; i < sz; i++) {
		hsh = ((31 * hsh - pw[gz] * (int) s[i - gz] + s[i]) % MOD1 + MOD1) % MOD1;
		ans += get(hsh);
	}
	out << ans;
	return 0;
}