Cod sursa(job #177393)

Utilizator razvi9Jurca Razvan razvi9 Data 12 aprilie 2008 20:58:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<cstdio>
#include<cstring>
const int hash1=1009;
const int hash2=1013;
const int hash3=11003;
int a[hash1][hash2][10],l,x,y,z,nr,n,c1,c2,c3,i;
char s[10000000],s2[21];
inline bool seek()
{
	for(int j=1;j<=a[x][y][0];j++)
		if(a[x][y][j]==z) return 1;
	return 0;
}
int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	gets(s);
	gets(s2);
	l=strlen(s2);
	goto calc;
	while(!feof(stdin))
	{
		gets(s2);
calc:
		x=y=z=0;
		for(i=0;i<l;i++)
		{
			x*=3;y*=3;z*=3;
			x+=s2[i]-'a';
			y+=s2[i]-'a';
			z+=s2[i]-'a';
			while(x>=hash1) x-=hash1;
			while(y>=hash2) y-=hash2;
			while(z>=hash3) z-=hash3;
		}
		if(!seek()) a[x][y][++a[x][y][0]]=z;
	}
	n=strlen(s);
	x=y=z=0;c1=c2=c3=1;
	for(i=0;i<l;i++)
	{
		s[i]-='a';
		if(i<l-1)
		{
			c1*=3;
			c2*=3;
			c3*=3;
			while(c1>=hash1) c1-=hash1;
			while(c2>=hash2) c2-=hash2;
			while(c3>=hash3) c3-=hash3;
		}
		x*=3;y*=3;z*=3;
		x+=s[i];
		y+=s[i];
		z+=s[i];
		while(x>=hash1) x-=hash1;
		while(y>=hash2) y-=hash2;
		while(z>=hash3) z-=hash3;
	}
	if(seek()) nr++;
	for(;i<n;i++)
	{
		s[i]-='a';
		x-=c1*s[i-l];
		y-=c2*s[i-l];
		z-=c3*s[i-l];
		while(x<0) x+=hash1;
		while(y<0) x+=hash2;
		while(z<0) x+=hash3;
		x*=3;y*=3;z*=3;
		x+=s[i];y+=s[i];z+=s[i];
		while(x>=hash1) x-=hash1;
		while(y>=hash2) y-=hash2;
		while(z>=hash3) z-=hash3;
		if(seek())nr++;
	}
	printf("%d\n",nr);
	fclose(stdout);
	return 0;
}