Cod sursa(job #102866)

Utilizator slayer4uVictor Popescu slayer4u Data 14 noiembrie 2007 19:10:24
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.91 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;

unsigned int cuvant_curent, x[50010], puteri[21]={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;
char text[10000010], man[32];

int cautbin(int val)
{
    int i, step;
    for (step = 1; step < n; step <<= 1);
    for (i = 1; step; step >>= 1)
        if (i + step < n && x[i + step] <= val)
           i += step;
    return i;
}
/*
int cautbin(int st, int dr)
{
	if ((dr - st == 1) || (st == dr))
	{
		if (x[st] == cuvant_curent) return st;
		else
		if (x[dr] == cuvant_curent) return dr;
		else
			return 0;
	}
	else
	{
		int m = (st + dr) / 2;
		if (cuvant_curent > x[m])
			return cautbin(m + 1, dr);
		else
		if (cuvant_curent < x[m])
			return cautbin(st, m - 1);
		else
			return m;
	}
}
*/
int main()
{
	freopen ("abc2.in", "rt", stdin);
	freopen ("abc2.out", "wt", stdout);

	fgets(text, 10000010, stdin);
	fgets(man, 32, stdin);
	p = 1;
	o = strlen(man) - 2;
	n ++;
	//for (i = 0; i <= 20; i ++)
		//printf("%.0lf,",pow((long double)3,(long double)i));
	for (i = 0; i <= o; i ++)
	{
		x[n] +=(unsigned int) puteri[i] * (man[i] - 'a');
	}
	while (fgets(man, 21, stdin))
	{
		n ++;
		for (i = 0; i <= o; i ++)
		{
			x[n] +=(unsigned int) puteri[i] * (man[i] - 'a');
		}
	}
	sort(x + 1, x + n + 1);

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

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

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