Cod sursa(job #497425)

Utilizator katakunaCazacu Alexandru katakuna Data 2 noiembrie 2010 15:46:27
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;

#define Nmax 10000010
#define Lmax 22
#define baza 3
#define MOD 666013

unsigned int n, l, sol;
unsigned int pow[Lmax];
char A[Nmax], B[Lmax];

vector <unsigned int> H[MOD + 10];

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

int find (unsigned int val) {
	
	int p = val % MOD;
    for (vector <unsigned int>::iterator it = H[p].begin (); it != H[p].end (); it++)
		if (*it == val)
			return 1;

	return 0;
}

void rezolva () {
	
	unsigned int i, nr = 0;
	for (i = 0; i < n; i++) {
		if (i >= l) nr-= pow[l-1] * (A[i - l] - 'a');
		nr = nr * baza + A[i] - 'a';
		if (i >= l - 1) sol+= find (nr);
	}

	printf ("%u", sol);
}

int main () {

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

	unsigned nr, i;

    scanf ("%s", A); n = strlen (A);
	scanf ("%s", B); l = strlen (B);

	pow[0] = 1;
	for (i = 1; i <= l; i++)
		pow[i] = pow[i-1] * baza;

	while (!feof (stdin)) {
		nr = 0;
		for (i = 0; i < l; i++) 
			nr+= (pow[l - (i + 1)] * (B[i] - 'a'));
		add_hash (nr);
		scanf ("%s", B);
	}

	rezolva ();

	return 0;
}