Cod sursa(job #497645)

Utilizator Addy.Adrian Draghici Addy. Data 2 noiembrie 2010 23:17:10
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define LMAX 10000050
#define MAX 32
#define MOD 666013
#define Z 3

char A[LMAX], B[MAX]; int n, m, i, nr;
unsigned int P[MAX], x, y;
vector <unsigned int> H[MOD];

int cauta (unsigned int); void adauga (unsigned int);

int main () {
	
	freopen ("abc2.in", "r", stdin);
	freopen ("abc2.out", "w", stdout);
	
	scanf ("%s", A); n = strlen (A);
	scanf ("%s", B); m = strlen (B);
	
	P[0] = 1;
	for (i = 1; i < m; i++)
		P[i] = P[i-1] * Z;	
	
	for (i = 0; i < m; i++)
		x += P[i] * (B[i] - 'a');
	adauga (x);
	
	while (!feof (stdin)) {
		scanf ("%s", B); x = 0;
		
		for (i = 0; i < m; i++)
			x += P[i] * (B[i] - 'a');
		
		adauga (x);
	}
	
	for (i = 0; i < m; i++)
		y += P[i] * (A[i] - 'a');
	nr += cauta (y);
	
	for (i = m; i < n; i++) {
		y = (y - (A[i-m] - 'a')) / Z + P[m-1] * (A[i] - 'a');
		nr += cauta (y);
	}
	
	printf ("%d", nr);
	
	return 0;
}

void adauga (unsigned int x) {
	
	int y = x % MOD;
	for (vector <unsigned int>::iterator it = H[y].begin (); it != H[y].end (); it++)
		if (*it == x)
			return;
	
	H[y].push_back (x);
}

int cauta (unsigned int x) {
	
	int y = x % MOD;
	for (vector <unsigned int>::iterator it = H[y].begin (); it != H[y].end (); it++)
		if (*it == x)
			return 1;
	
	return 0;
}