Cod sursa(job #497210)

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

long n,m,nr,sol1,pow1,i,M1,M2,sol2,pow2;

struct hash
{
	long nod;
	hash *link;
}*H1[45000],*H2[45000];

char str[10000005],s[25];

void add1(long x)
{
	hash *p;
	p=new hash;
	p->nod=x;
	p->link=H1[x%M1];
	H1[x%M1]=p;
}

long src1(long x)
{
	hash *p;
	p=H1[x%M1];
	while(p!=NULL)
	{
		if(p->nod==x) return 1;
		p=p->link;
	}
	return 0;
}

void add2(long x)
{
	hash *p;
	p=new hash;
	p->nod=x;
	p->link=H2[x%M2];
	H2[x%M2]=p;
}

long src2(long x)
{
	hash *p;
	p=H2[x%M2];
	while(p!=NULL)
	{
		if(p->nod==x) return 1;
		p=p->link;
	}
	return 0;
}

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

	fgets(str,10000005,stdin);
	M1=44027;
	M2=43997;
	n=strlen(str)-1;
	if(str[n]=='\n') n--;
	fgets(s,25,stdin);
	m=strlen(s)-1;
	if(s[m]=='\n') m--;
	sol1=0;
	sol2=0;
	for(i=0;i<=m;i++)
	{
		sol1=((sol1*4)%M1+s[i]-'a')%M1;
		sol2=((sol2*4)%M2+s[i]-'a')%M2;
	}
	if(src1(sol1)==0&&src2(sol2)==0)
	{
		add1(sol1);
		add2(sol2);
	}
	while(!feof(stdin))
	{
		fgets(s,25,stdin);
		if(!feof(stdin))
		{
			sol1=0;
			sol2=0;
			for(i=0;i<=m;i++)
			{
				sol1=((sol1*4)%M1+s[i]-'a')%M1;
				sol2=((sol2*4)%M2+s[i]-'a')%M2;
			}
			if(src1(sol1)==0&&src2(sol2)==0)
			{
				add1(sol1);
				add2(sol2);
			}
		}
	}

	sol1=0;
	sol2=0;
	pow1=1;
	pow2=1;
	nr=0;
	for(i=1;i<=m;i++)
	{
		pow1=(pow1*4)%M1;
		pow2=(pow2*4)%M2;
	}
	for(i=0;i<=m;i++)
	{
		sol1=((sol1*4)%M1+str[i]-'a')%M1;
		sol2=((sol2*4)%M2+str[i]-'a')%M2;
	}
	if(src1(sol1)&&src2(sol2)) nr++;
	for(i=m+1;i<=n;i++)
	{
		sol1=(((sol1+M1-(pow1*(str[i-m-1]-'a'))%M1)%M1)*4+(str[i]-'a'))%M1;
		sol2=(((sol2+M2-(pow2*(str[i-m-1]-'a'))%M2)%M2)*4+(str[i]-'a'))%M2;
		if(src1(sol1)&&src2(sol2)) nr++;
	}
	printf("%ld\n",nr);

	return 0;
}