Cod sursa(job #498342)

Utilizator ZethpixZethpix Zethpix Data 4 noiembrie 2010 21:49:49
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <string.h>

unsigned int m,n,i,pos,sol,pow,nr,M;
char string[10000010],s[25];

struct hash
{
	unsigned int nod;
	hash *link;
}*H[700000];

inline void add(unsigned int pos,unsigned int sol)
{
	hash *p;
	p=new hash;
	p->nod=sol;
	p->link=H[pos];
	H[pos]=p;
}

inline int find(unsigned int pos,unsigned int sol)
{
	hash *p;
	p=H[pos];
	while(p!=NULL)
	{
		if(p->nod==sol) return 1;
		p=p->link;
	}
	return 0;
}

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

	fgets(string,10000010,stdin);
	n=strlen(string)-2;

	M=666013;
	fgets(s,25,stdin);
	m=strlen(s)-2;
	pos=0;
	sol=0;
	for(i=0;i<=m;i++)
	{
		pos*=3;
		sol*=3;
		pos+=s[i]-'a';
		sol+=s[i]-'a';
		pos%=M;
	}
	add(pos,sol);

	while(!feof(stdin))
	{
		fgets(s,25,stdin);
		pos=0;
		sol=0;
		for(i=0;i<=m;i++)
		{
			pos*=3;
			sol*=3;
			pos+=s[i]-'a';
			sol+=s[i]-'a';
			pos%=M;
		}
		add(pos,sol);
	}

	pos=0;
	sol=0;
	for(i=0;i<=m;i++)
	{
		pos*=3;
		sol*=3;
		pos+=string[i]-'a';
		sol+=string[i]-'a';
		pos%=M;
	}
	add(pos,sol);

	pow=1;
	for(i=1;i<=m;i++) pow*=3;

	nr=0;
	for(i=m+1;i<=n;i++)
	{
		pos+=M;
		pos-=pow*(string[i-m-1]-'a');
		pos*=3;
		pos+=string[i]-'a';
		pos%=M;
		sol-=pow*(string[i-m-1]-'a');
		sol*=3;
		sol+=string[i]-'a';
		if(find(pos,sol)) nr++;
	}

	printf("%d\n",nr);

	return 0;
}