Cod sursa(job #343879)

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

using namespace std;

vector<int> h[MOD];

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

bool find(int key)
{
	int i;
	int k = key % MOD;
	for (i=0;i<h[k].size();i++)
	{
		if (h[k][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;

	fgets(text,MAXN,stdin);

	len = strlen(text)-1;
	fgets(cv,CLEN,stdin);
	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;
		fgets(cv,CLEN,stdin);
		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;
}