Cod sursa(job #498060)

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

unsigned long long H[10000000],key,sol,nr,m,n,pow;
long i;
char s[25],string[10000010];

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--;
	fgets(s,25,stdin);
	m=strlen(s)-1;
	if(s[m]=='\n') m--;

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

	key=0;
	pow=1;
	for(i=1;i<=m;i++)
		pow*=3;
	sol=0;
	for(i=0;i<=m;i++)
		key=key*3+string[i]-'a';
	if(H[key]) sol++;
	for(i=m+1;i<=n;i++)
	{
		key=(key-(string[i-m-1]-'a')*pow)*3+string[i]-'a';
		if(H[key]) sol++;
	}
	printf("%lld\n",sol);

	return 0;
}