Cod sursa(job #498354)

Utilizator ZethpixZethpix Zethpix Data 4 noiembrie 2010 22:00:07
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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*=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);

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

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

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

	return 0;
}