Cod sursa(job #219676)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 8 noiembrie 2008 00:23:22
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;

#define MOD 666013

char s[10000505], cuv[205];
int rez, p[205], w[50005], n, k, nr;

vector<int> hash[MOD];

int find(int x)
{
	int poz = x % MOD, l = hash[poz].size();
	for (int i = 0; i < l; 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 <= k; 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 main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);

	int i, j, x;

	putere();

	fgets(s,10000501,stdin);
	fgets(cuv,200,stdin);
	k = strlen(cuv) - 1;
	n = strlen(s) - 1;

	x = transform(cuv, k);
	hash[x % MOD].push_back(x);
	while (!feof(stdin))
	{
		fgets(cuv,200,stdin);
		x = transform(cuv,k);
		hash[x % MOD].push_back(x);
	}

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

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