Cod sursa(job #498371)

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

unsigned m,n,i,sol,pow,nr,M;
char string[10000010],s[25];

struct hash
{
	unsigned nod;
	hash *link;
}*H[100000];

inline void add(unsigned sol)
{
	hash *p;
	p=new hash;
	p->nod=sol;
	p->link=H[sol%M];
	H[sol%M]=p;
}

inline int find(unsigned sol)
{
	hash *p;
	p=H[sol%M];
	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)-1;
	if(string[n]=='\n') n--;

	M=99987;
	fgets(s,25,stdin);
	m=strlen(s)-1;
	if(s[m]=='\n') m--;
	sol=0;
	for(i=0;i<=m;i++)
		sol=sol*3+s[i]-'a';
	add(sol);

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

	sol=0;
	for(i=0;i<=m;i++)
		sol=sol*3+string[i]-'a';
	add(sol);

	pow=1;
	for(i=1;i<=m;i++) pow*=3;

	nr=0;
	if(find(sol)) nr++;
	for(i=m+1;i<=n;i++)
	{
		sol=sol*3-pow*(string[i-m-1]-'a')*3+(string[i]-'a');
		if(find(sol)) nr++;
	}

	printf("%u\n",nr-1);

	return 0;
}