Cod sursa(job #343903)

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

using namespace std;

vector<int> h[MOD];
char text[MAXN];

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 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;
	}
	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);
	}
	
	key = 0;
	pw = 1;

	for (i=0;i<sz;i++)
	{
		key+= (text[i] - 'a')*pw;
		pw*=3;
	}
	pw/=3;
	
	if (find(key))
	{
		nrsol++;
	}

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