Cod sursa(job #2297379)

Utilizator flibiaVisanu Cristian flibia Data 5 decembrie 2018 19:25:39
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>
#pragma GCC optimize("03")
#define MOD1 24697 
#define MOD2 24709

using namespace std;

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

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

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

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

int main() {
	pw1[0] = pw2[0] = 1;
	for (int i = 1; i <= 21; i++) {
		pw1[i] = (pw1[i - 1] * 3) % MOD1;
		pw2[i] = (pw2[i - 1] * 3) % MOD2;
	}
	in >> s;
	while (in >> g) {
		gz = strlen(g);
		int hsh1 = 0, hsh2 = 0;
		for (int i = 0; i < gz; i++) {
			hsh1 = (hsh1 + (int) g[i] * pw1[gz - i - 1]) % MOD1;
			hsh2 = (hsh2 + (int) g[i] * pw2[gz - i - 1]) % MOD2;
		}
		baga(hsh1, hsh2);
	}
	sz = strlen(s);
	int hsh1 = 0, hsh2 = 0;
	for (int i = 0; i < gz; i++) {
		hsh1 = (hsh1 + (int) s[i] * pw1[gz - i - 1]) % MOD1;
		hsh2 = (hsh2 + (int) s[i] * pw2[gz - i - 1]) % MOD2;
	}
	ans += get(hsh1, hsh2);
	for (int i = gz; i < sz; i++) {
		hsh1 = ((3 * hsh1 - pw1[gz] * (int) s[i - gz] + s[i]) % MOD1 + MOD1) % MOD1;
		hsh2 = ((3 * hsh2 - pw2[gz] * (int) s[i - gz] + s[i]) % MOD2 + MOD2) % MOD2;
		ans += get(hsh1, hsh2);
	}
	out << ans;
	return 0;
}