Cod sursa(job #112538)

Utilizator slayer4uVictor Popescu slayer4u Data 5 decembrie 2007 22:05:45
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int HASH_THINGY = 47; 

unsigned int cuvant_curent, x[47][60010], puteri[]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467,3486784401};
int p, o, n, i, j, candidati, k, poz, crap;
char text[11000000], man[42];

inline int cautbin(int moo, int st, int dr)
{
	int m;
	for (; st <= dr; )
	{
		m = (st + dr) >> 1;
		if (cuvant_curent == x[moo][m])
			return m;
		if (cuvant_curent > x[moo][m])
			st = m + 1;
		else
			dr = m - 1;
	}
	return 0;
}

int main()
{
	freopen ("abc2.in", "rt", stdin);
	freopen ("abc2.out", "wt", stdout);

	fgets(text, 11000000, stdin);
	fgets(man, 32, stdin);
	p = 1;
	o = strlen(man) - 2;
	n ++;
	crap = 0;
	for (i = 0; i <= o; i ++)
	{
		crap += puteri[i] * (man[i] - 'a');
	}
	x[crap % HASH_THINGY][++ x[crap % HASH_THINGY][0]] = crap;

	while (fgets(man, 32, stdin))
	{
		n ++;
		crap = 0;
		for (i = 0; i <= o; i ++)
		{
			crap += puteri[i] * (man[i] - 'a');
		}
		x[crap % HASH_THINGY][++ x[crap % HASH_THINGY][0]] = crap;
	}
	for (i = 0; i < HASH_THINGY; i ++)
		sort(x[i] + 1, x[i] + x[i][0] + 1);

	for (i = 0; i <= o; i ++)
			cuvant_curent += puteri[i] * (text[i] - 'a');

	k = strlen(text) - 1;
	for (; i <= k; i ++)
	{
		poz = cautbin(cuvant_curent % HASH_THINGY, 1, x[cuvant_curent % HASH_THINGY][0]);
		if (poz)
			candidati ++;
		cuvant_curent = (cuvant_curent - (text[i - o - 1] - 'a')) / 3 + puteri[o] * (text[i] - 'a');
	}

	poz = cautbin(cuvant_curent % HASH_THINGY, 1, x[cuvant_curent % HASH_THINGY][0]);
		if (poz)
			candidati ++;

	printf("%ld\n", candidati);
	return 0;
}