Cod sursa(job #1471474)

Utilizator theprdvtheprdv theprdv Data 14 august 2015 05:03:38
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 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) if(G) for ( hash_line* it = (G) ; it; it = it->next)

using namespace std;

int N, NB, ans, P1 = 1, P2 = 1, P3 = 1, set = 0;
char A[MAXA], B[MAXB];

struct hash_line{
	int val1, val2;
	hash_line* next;
} *Hash[MOD];

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

inline void insert_val(int key, int val1, int val2){
	int list = key % MOD;
	foreach(Hash[list]) if (it->val1 == val1 && it->val2 == val2) return;

	hash_line *New = new hash_line;
	New->val1 = val1, New->val2 = val2, New->next = Hash[list];
	Hash[list] = New;
}


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_val(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 += find_val(hash1, hash2, hash3);
	}
	
	
	printf("%d\n", ans);
	return 0;
}