Cod sursa(job #344056)

Utilizator prdianaProdan Diana prdiana Data 28 august 2009 12:42:37
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXN 10000002
#define MAXL 22
#define MOD 666013

using namespace std;

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

inline void hash(int key)
{
	h[key % MOD].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);
	
	gets(text);
	int len;
	int tlen,i,key,nrsol = 0;
	tlen = strlen(text);
	while (gets(wr))
	{
		len = strlen(wr);
		key = 0;
		for (i=0;i<len;i++)
		{
			key = key*3 + wr[i]- 'a';
		}
		hash(key);
	}
	key = 0;
	int pw =1;
	for (i=0;i<len;i++)
	{
		key = key*3 + text[i] - 'a';
		pw*=3;
	}
	pw/=3;

	if (find(key))
	{
		nrsol++;
	}

	for (i=1;i<=tlen-len;i++)
	{
		key = (key - (text[i-1] - 'a')*pw) * 3 + (text[i+len-1] -'a');

		if (find(key))
		{
			nrsol++;
		}
	}
	
	printf("%d",nrsol);

	return 0;
}