Cod sursa(job #1471471)

Utilizator theprdvtheprdv theprdv Data 14 august 2015 03:47:07
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#define _CRT_SECURE_NO_DEPRECATE
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAXA 10000005
#define MAXB 50005
#define P 73
#define MOD 25000
#define MOD1 100003
#define MOD2 1000021
#define MOD3 1000051
#define foreach(G) for(decltype((G).begin()) it = (G).begin(); it != (G).end(); ++it)

using namespace std;

int N, NB, ans, P1 = 1, P2 = 1, P3 = 1, set = 0;
char A[MAXA], B[MAXB];
vector <pair<int, int>> Hash[MOD];

inline void insert_hash(int key, int val1, int val2){
	foreach(Hash[key % MOD])
		if (it->first == val1 && it->second == val2) return;
	Hash[key % MOD].push_back(make_pair(val1, val2));
}

inline int search_hash(int key, int val1, int val2){
	foreach(Hash[key % MOD])
		if (it->first == val1 && it->second == val2) return 1;
	return 0;
}

int main(){
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);

	int hash1, hash2, hash3, len = 0;
	gets(A);
	N = strlen(A);

	while (fgets(B, MAXB, stdin)){
		if (!len) len = strlen(B) - 1;
		hash1 = hash2 = hash3 = 0;
		if (!NB) NB = len;

		for (int i = 0; i < len; ++i){
			hash1 = (hash1 * P + B[i]) % MOD1;
			hash2 = (hash2 * P + B[i]) % MOD2;
			hash3 = (hash3 * P + B[i]) % MOD3;

			if (i && !set) P1 = (P1 * P) % MOD1, P2 = (P2 * P) % MOD2, P3 = (P3 * P) % MOD3;
		}
		set = 1;
		insert_hash(hash1, hash2, hash3);
	}

	hash1 = hash2 = hash3 = 0;

	for (int i = 0; i < N; ++i){
		if (i >= NB)
			hash1 = hash1 - (A[i - NB] * P1) % MOD1 + MOD1,
			hash2 = hash2 - (A[i - NB] * P2) % MOD2 + MOD2,
			hash3 = hash3 - (A[i - NB] * P3) % MOD3 + MOD3;
		
		hash1 = (hash1 * P + A[i]) % MOD1;
		hash2 = (hash2 * P + A[i]) % MOD2;
		hash3 = (hash3 * P + A[i]) % MOD3;

		if (i >= NB - 1) ans += search_hash(hash1, hash2, hash3);
	}
	
	
	printf("%d\n", ans);
	return 0;
}