Cod sursa(job #219666)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 7 noiembrie 2008 23:26:51
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <string.h>

char s[10000005], cuv[25];
int rez, p[25];

typedef struct nod
{
	int x;
	nod *a;
} *pNod;
pNod v[10000];

void putere()
{
	int i;
	p[0] = 1;
	for (i = 1; i <= 20; i++) p[i] = p[i - 1] * 3;
}

void add(int x)
{
	int poz = x % 9997;
	pNod q = new nod;
	q -> x = x;
	q -> a = v[poz];
	v[poz] = q;
}

int caut(int x)
{
	int c = 0, poz = x % 9997;
	pNod q;
	for (q = v[poz]; q != NULL; q = q -> a) if (q -> x == x) c++;
	return c;
}

int transform(char s[], int n)
{
	int x = 0, i;
	for (i = 0; i < n; i++) x += (s[i] - 'a') * p[n - i - 1];
	return x;
}


int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);

	int n, k, i, j, x;

	putere();

	fgets(s,10000001,stdin);
	fgets(cuv,25,stdin);
	k = strlen(cuv) - 1;
	n = strlen(s) - 1;

	x = 0;

	for (i = 0; i < k; i++) x += (s[i] - 'a') * p[k - i - 1];
	add(x);
	for (i = 1; i < n - k; i++)
	{
		x -= ((s[i - 1] - 'a')* p[k - 1]);
		x *= 3;
		x += (s[i + k] - 'a');
		add(x);
	}

	x = transform(cuv, k);
	rez += caut(x);

	while (!feof(stdin))
	{
		fgets(cuv,25,stdin);
		x = transform(cuv,k);
		rez += caut(x);
	}

	printf("%d\n",rez);
	return 0;
}