Cod sursa(job #227940)

Utilizator ProtomanAndrei Purice Protoman Data 5 decembrie 2008 22:35:29
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#define mx 10000010
#define mxv 50010

using namespace std;

int nm, el, h, rez;
unsigned int x, bz3;
unsigned int vct[mxv];
char s[mx + 4];
char s1[32];

int cauta(unsigned int val)
{
	int step = 1, rez = 1;
	for (step = 1; step < el; step <<= 1);
	for (; step; step >>= 1)
		if (rez + step <= el && vct[rez + step] <= val)
			rez += step;
	if (vct[rez] == val)
		return 1;
	return 0;
}

int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	fgets(s, mx + 2, stdin);
	nm = strlen(s) - 1;
	while (fgets(s1, 32, stdin))
	{
		h = strlen(s1) - 1;
		x = 0;
		for (int i = 0; i < h; i++)
			x = x * 3 + s1[i] - 'a';
		vct[++el] = x;
	}
	sort(vct + 1, vct + 1 + el);
	bz3 = 1;
	for (int i = 0; i < h; i++)
		bz3 *= 3;
	x = 0;
	for (int i = 0; i < nm; i++)
	{
		x = x * 3 + (s[i] - 'a');
		if (i >= h)
			x -= bz3 * (s[i - h] - 'a');
		if (i > h - 2)
			rez += cauta(x);
	}
	printf("%d\n", rez);
	fclose(stdin);
	fclose(stdout);
	return 0;
}