Cod sursa(job #112606)

Utilizator slayer4uVictor Popescu slayer4u Data 6 decembrie 2007 09:31:31
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

const int HASH_THINGY = 128 * 1024;
vector <int> x[HASH_THINGY];
unsigned int cuvant_curent, 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];

const unsigned int prime = 101;
inline unsigned int hash_fun(unsigned int value) {
	return (prime * value) & (HASH_THINGY - 1);
}

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 + 1;
		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[hash_fun(crap)].push_back(crap);

	while (fgets(man, 32, stdin))
	{
		n ++;
		crap = 0;
		for (i = 0; i <= o; i ++)
		{
			crap += puteri[i] * (man[i] - 'a');
		}
		x[hash_fun(crap)].push_back(crap);
	}
	for (i = 0; i < HASH_THINGY; i ++) if (!x[i].empty()) {
		sort(x[i].begin(), x[i].end());
		x[i].erase(unique(x[i].begin(), x[i].end()), x[i].end());
	}

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

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

	poz = cautbin(hash_fun(cuvant_curent), 0, x[hash_fun(cuvant_curent)].size() - 1);
		if (poz)
			candidati ++;

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