Cod sursa(job #497699)

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

struct hash
{
	long nod;
	hash *link;
}*H[9973];

long nr,n,m,i,sol1,sol2,M1,M2,pow1,pow2;
hash *p;
char string[10000010],s[25];

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

	fgets(string,10000010,stdin);
	n=strlen(string)-1;
	if(string[n]=='\n') n--;
	fgets(s,25,stdin);
	m=strlen(s)-1;
	if(s[m]=='\n') m--;
	sol1=0;
	sol2=0;
	M1=9973;
	M2=999983;
	for(i=0;i<=m;i++)
	{
		sol1=(sol1*3+s[i])%M1;
		sol2=(sol2*3+s[i])%M2;
	}
	p=new hash;
	p->nod=sol2;
	p->link=H[sol1];
	H[sol1]=p;
	while(!feof(stdin))
	{
		fgets(s,25,stdin);
		sol1=0;
		sol2=0;
		for(i=0;i<=m;i++)
		{
			sol1=(sol1*3+s[i])%M1;
			sol2=(sol2*3+s[i])%M2;
		}
		p=new hash;
		p->nod=sol2;
		p->link=H[sol1];
		H[sol1]=p;
	}

	nr=0;
	sol1=0;
	sol2=0;
	for(i=0;i<=m;i++)
	{
		sol1=(sol1*3+string[i])%M1;
		sol2=(sol2*3+string[i])%M2;
	}
	pow1=1;
	pow2=1;
	for(i=1;i<=m;i++)
	{
		pow1=(pow1*3)%M1;
		pow2=(pow2*3)%M2;
	}
	p=H[sol1];
	while(p!=NULL)
	{
		if(p->nod==sol2)
		{
			nr++;
			break;
		}
		p=p->link;
	}
	for(i=m+1;i<=n;i++)
	{
		sol1=((sol1+M1-(pow1*string[i-m-1])%M1)*3+string[i])%M1;
		sol2=((sol2+M2-(pow2*string[i-m-1])%M2)*3+string[i])%M2;
		p=H[sol1];
		while(p!=NULL)
		{
			if(p->nod==sol2)
			{
				nr++;
				break;
			}
			p=p->link;
		}
	}
	printf("%ld\n",nr);

	return 0;
}