Cod sursa(job #531198)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 9 februarie 2011 09:42:10
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIMN 10000002
#define DIMC2 50002
#define DIMC 22

char S[DIMN], C[DIMC];
int LN, LC, NC, Ct;
unsigned int HS, HC[DIMC2], P = 1;

int codif (char s[])
{
	int h = 0;
	for (int i = 0; i < LC; i++)
		h = h * 3 + s[i] - 'a';
	return h;
}

void elim_dubl ()
{
	int i, j;
	for (i = 1, j = 0; i <= NC; i++)
		if (HC[i] != HC[i - 1])
			HC[++j] = HC[i];
	NC = j;
}

int cauta (int val)
{
	int p = 0, u = NC, m;
	while (p <= u)
	{
		m = p + (u - p) / 2;
		if (HC[m] <= val)
			p = m + 1;
		else
			u = m - 1;
	}
	return (u >= 0 && u <= NC) ? u : -1;
}

int main ()
{
	int i, p;
	freopen ("abc2.in", "r", stdin);
	freopen ("abc2.out", "w", stdout);
	
	fgets (S, DIMN, stdin);
	fgets (C, DIMC, stdin);

	for (LN = 0; S[LN] >= 'a' && S[LN] <= 'c'; LN++);
	for (LC = 0; C[LC] >= 'a' && C[LC] <= 'c'; LC++, P *= 3);
	P /= 3;
	
	HC[0] = codif (C);	
	while (	fgets (C, DIMC, stdin) )
		HC[++NC] = codif (C);
	
	sort (HC, HC + NC + 1);
	elim_dubl ();

	LN = LN - LC + 1;
	HS = codif (S);
	p = cauta (HS);
	if (p != -1)
		if (HC[p] == HS)
			Ct++;	
	for (i = 1; i < LN; i++)
	{
		HS = (HS - (S[i - 1]-'a') * P) * 3 + (S[i + LC - 1]-'a'); 
		p = cauta (HS);
		if (p != -1)
			if (HC[p] == HS)
				Ct++;
	}
	
	printf ("%d", Ct);
	
	return 0;
}