Cod sursa(job #498359)

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

unsigned int m,n,i,pos,sol,pow1,nr,M,pow2;
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=(pos*4+s[i]-'a')%M;
		sol=sol*4+s[i]-'a';
	}
	add(pos,sol);

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

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

	pow1=1;
	pow2=1;
	for(i=1;i<=m;i++)
	{
		pow1*=4;
		pow1%=M;
		pow2*=4;
	}

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

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

	return 0;
}