Cod sursa(job #219670)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 8 noiembrie 2008 00:01:56
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char s[10000005], cuv[25];
int rez, p[25], w[500005], n, k;

int hash[10000][50];

void add(int x)
{
	int poz = x % 9997, i, ok;
	if (!hash[poz][0])
	{
		hash[poz][0]++;
		hash[poz][1] = x;
	}
	else
	{
		ok = 1;
		for (i = 1; i <= hash[poz][0]; i++) if (hash[poz][i] == x) ok = 0;
		if (ok) hash[poz][++hash[poz][0]] = x;
	}
}

int cauta(int x)
{
	int poz = x % 9997;
	for (int i = 1; i <= hash[poz][0]; i++) if (hash[poz][i] == x) return 1;
	return 0;
}

int cmp(const void *i, const void *j)
{
	return *(int*)i - *(int*)j;
}

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

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 caut(int x)
{
	int p, u, m, cnt = 0;
	p = 0; u = n - k + 1;
	while (p <= u)
	{
		m = (p + u) / 2;
		if (w[m] == x) break;
		if (w[m] < x) p = m + 1;
		else u = m - 1;
	}
	if (p > u) return 0;
	while (w[m] == x) m--;
	m++;
	for (; w[m] == x; m++) cnt++;
	return cnt;
}



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

	int 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];
	w[0] = x;
	for (; i < n; i++)
	{
		x -= ((s[i - k] - 'a') * p[k - 1]);
		x *= 3;
		x += (s[i] - 'a');
		w[i - k + 1] = x;
	}
	qsort(w,n - k + 1,sizeof(int),cmp);

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

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

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