Cod sursa(job #497238)

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

int n,m,nr,sol,pow,i,M,powx,solx;

struct hash
{
	int nod,nodx;
	hash *link;
}*H[10000];

char str[10000005],s[25];

void add(int x,int xx)
{
	hash *p;
	p=new hash;
	p->nod=x;
	p->nodx=xx;
	p->link=H[x%M];
	H[x%M]=p;
}

int src(int x,int xx)
{
	hash *p;
	p=H[x%M];
	while(p!=NULL)
	{
		if(p->nod==x&&p->nodx==xx) return 1;
		p=p->link;
	}
	return 0;
}

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

	fgets(str,10000005,stdin);
	M=9923;
	n=strlen(str)-1;
	if(str[n]=='\n') n--;
	fgets(s,25,stdin);
	m=strlen(s)-1;
	if(s[m]=='\n') m--;
	sol=0;
	for(i=0;i<=m;i++)
	{
		sol=((sol*3)%M+s[i])%M;
		solx=((solx*5)%M+s[i])%M;
	}
	add(sol,solx);
	while(!feof(stdin))
	{
		fgets(s,25,stdin);
		if(!feof(stdin))
		{
			sol=0;
			for(i=0;i<=m;i++)
			{
				sol=((sol*3)%M+s[i])%M;
				solx=((solx*5)%M+s[i])%M;
			}
			add(sol,solx);
		}
	}

	sol=0;
	solx=1;
	pow=1;
	powx=1;
	nr=0;
	for(i=1;i<=m;i++)
	{
		pow=(pow*3)%M;
		powx=(powx*5)%M;
	}
	for(i=0;i<=m;i++)
	{
		sol=((sol*3)%M+str[i])%M;
		solx=((solx*5)%M+str[i])%M;
	}
	if(src(sol,solx)) nr++;
	for(i=m+1;i<=n;i++)
	{
		sol=(((sol+M-(pow*str[i-m-1])%M)%M)*3+str[i])%M;
		solx=(((solx+M-(powx*str[i-m-1])%M)%M)*5+str[i])%M;
		if(src(sol,solx)) nr++;
	}
	printf("%d\n",nr);

	return 0;
}