Cod sursa(job #343876)

Utilizator prdianaProdan Diana prdiana Data 27 august 2009 17:10:45
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXN 1002
#define CLEN 22
#define MOD 666013

using namespace std;

vector<int> h[MOD];

void hash(int key)
{
	h[key % MOD].push_back(key);
}

bool find(int key)
{
	int i;
	for (i=0;i<h[key % MOD].size();i++)
	{
		if (h[key % MOD][i] == key)
		{
			return true;
		}
	}
	return false;
}

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

	char text[MAXN];
	char cv[CLEN];
	int len,i,j,sz,pw,key = 0,nrsol = 0;

	gets(text);

	len = strlen(text)-1;
	gets(cv);
	sz = strlen(cv)-1;
	pw = 1;
	for (i=0;i<sz;i++)
	{
		key += (cv[i]-'a')*pw;
		pw*=3;
	}
	hash(key);
	while (!feof(stdin))
	{
		key = 0;
		pw = 1;
		gets(cv);
		for (i=0;i<sz;i++)
		{
			key+= (cv[i] - 'a')*pw;
			pw*=3;
		}
		hash(key);
	}

	for (i=0;i<len-sz;i++)
	{
		key = 0;
		pw = 1;
		for (j=0;j<sz;j++)
		{
			key+= (text[i+j] - 'a')*pw;
			pw*=3;
		}
		if (find(key))
		{
			nrsol++;
		}
	}
	printf("%d",nrsol);
	return 0;
}