Cod sursa(job #102126)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 14 noiembrie 2007 00:08:04
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.15 kb
#include <cstdio>

#define fin  "abc2.in"
#define fout "abc2.out"

const int mod  = 387231;
const int Nmax = 100;
const int Mmax = 10000010;

int N,ret,h[mod];
char buff[Nmax];
char txt[Mmax];

void ins(char a[])
{
	int i,pt,hs;

	pt=1;

	hs=0;

	for ( i=N-1;i>=0;--i )
	{
		hs = ( hs + ( a[i] - 'a' ) * pt ) % mod ;
		pt = pt * 3 % mod;
	}
	
//	for (i=0;i<N;++i)
//		printf("%c",buff[i]);
//	printf(" %d\n",hs);

	h[hs]=1;
}

int main()
{
	char c;
	int i,pt,hs;

	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	fgets(txt,Mmax,stdin);
	fgets(buff,Nmax,stdin);

	while ( buff[N] != '\n' ) ++ N ;

	ins(buff);

	while ( 1 ) 
	{
		fgets(buff,Nmax,stdin);
		if ( buff[0]!='a' && buff[0]!='b' && buff[0]!='c' )
			break ;
		ins(buff);
	}

	hs = 0 ;
	pt = 1;

	for ( i = N - 1 ; i >= 0 ; --i )
	{
		hs = ( hs + ( txt[i] - 'a' ) * pt % mod ) % mod;
		if ( i != 0 ) pt = pt * 3 % mod;
	}

//	printf("%d\n",hs);

	ret+=h[hs];

	for ( i = N ; txt[i] != '\n'; ++i )
	{
		hs = hs - pt * ( txt[i-N] - 'a' ) % mod;
		if ( hs < 0 ) hs += mod;
		hs = ( hs * 3 ) % mod;
		hs = ( hs + txt[i] - 'a' ) % mod; 

		ret += h[hs];

	//	printf("%d\n",hs);
	}

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

	return 0;
}