Cod sursa(job #103546)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 15 noiembrie 2007 14:17:35
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 3.46 kb
#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

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

const int mod1 = 775371;
const int mod2 = 695655;
const int mod3 = 883121;
const int mod4 = 963473;
const int mod5 = 677247;

const int p1 = 3, p2 = 5, p3 = 7, p4 = 11, p5 = 13;

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

int N,ret;
char h1[mod1],h2[mod2],h3[mod3],h4[mod4],h5[mod5];
char buff[Nmax];
char txt[Mmax];
char v[Mmax];

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

//hash1
	pt=1; hs=0;
	for ( i=N-1;i>=0;--i )
	{
		hs = ( hs + ( a[i] - 'a' ) * pt ) % mod1 ;
		pt = pt * p1 % mod1;
	}
	h1[hs]=1;
 
//hash2
	pt=1; hs=0;
	for ( i=N-1;i>=0;--i )
	{
		hs = ( hs + ( a[i] - 'a' ) * pt ) % mod2 ;
		pt = pt * p2 % mod2;
	}
	h2[hs]=1;
	
//hash3
	pt=1; hs=0;
	for ( i=N-1;i>=0;--i )
	{
		hs = ( hs + ( a[i] - 'a' ) * pt ) % mod3 ;
		pt = pt * p3 % mod3;
	}
	h3[hs]=1;

//hash4
	pt=1; hs=0;
	for ( i=N-1;i>=0;--i )
	{
		hs = ( hs + ( a[i] - 'a' ) * pt ) % mod4 ;
		pt = pt * p4 % mod4;
	}
	h4[hs]=1;
	
//hash5
    pt=1; hs=0;
	for ( i=N-1;i>=0;--i )
	{
		hs = ( hs + ( a[i] - 'a' ) * pt ) % mod5 ;
		pt = pt * p5 % mod5;
	}
	h5[hs]=1;
	
}

int main()
{
	int i,pt1,pt2,pt3,pt4,pt5,hs1,hs2,hs3,hs4,hs5;
	int tmp;

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

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

    memset(h1,0,sizeof(h1));
    memset(h2,0,sizeof(h2));
    memset(h3,0,sizeof(h3));
    memset(h4,0,sizeof(h4));
    memset(h5,0,sizeof(h5));
    
	for ( i = 0 ; 'a' <= txt[i] && txt[i]<='c' ; ++i )
		txt[i]-='a';

	while ( 'a' <= buff[N] && buff[N] <= 'c' ) ++ N ;

	ins(buff);

	while ( !feof(stdin) ) 
	{
		fgets(buff,Nmax,stdin);
		ins(buff);
	}

	hs1 = hs2 = hs3 = hs4 = hs5 = 0;
	
	pt1 = pt2 = pt3 = pt4 = pt5 = 1;

	for ( i = N - 1 ; i >= 0 ; --i )
	{
       	hs1 = ( hs1 + (txt[i])* pt1 ) % mod1;
		hs2 = ( hs2 + (txt[i])* pt2 ) % mod2;
		hs3 = ( hs3 + (txt[i])* pt3 ) % mod3;
		hs4 = ( hs4 + (txt[i])* pt4 ) % mod4;
		hs5 = ( hs5 + (txt[i])* pt5 ) % mod5;
		
        if ( i != 0 ) 
        { 
             pt1 = pt1 * p1 % mod1;
             pt2 = pt2 * p2 % mod2;
             pt3 = pt3 * p3 % mod3;
             pt4 = pt4 * p4 % mod4;
             pt5 = pt5 * p5 % mod5;
        }
	}

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

	ret = ret + ( h1[hs1] & h2[hs2] & h3[hs3] & h4[hs4] & h5[hs5] ) ; 

	memset(v,1,sizeof(v));
	
	for ( i = N ; 0 <= txt[i] && txt[i] <= 2 ; ++i )
	{ 
		tmp = pt1 * txt[i-N];
		if ( tmp >= mod1 ) tmp-=mod1;	
		hs1 = ( hs1  + mod1 - tmp ) * p1 + txt[i];
		hs1 = hs1 % mod1;
		v[i] = ( v[i] & h1[hs1] );		
	}
/*
	for ( i = N ; 'a' <= txt[i] && txt[i]<='z'; ++i )
	{ 
		hs2 = hs2 - pt2 * ( txt[i-N] -'a' )% mod2 ;
		if ( hs2 < 0 ) hs2 += mod2;
		hs2 = ( hs2 * p2 + txt[i] -'a') % mod2;        
		v[i] = ( v[i] & h2[hs2] );
	}

	for ( i = N ; 'a' <= txt[i] && txt[i]<='z'; ++i )
	{ 
		hs3 = hs3 - pt3 * ( txt[i-N] - 'a' ) % mod3 ;
		if ( hs3 < 0 ) hs3 += mod3;
		hs3 = ( hs3 * p3 + txt[i] - 'a' ) % mod3;        
		v[i] = ( v[i] & h3[hs3] );
	}

	for ( i = N ; 'a' <= txt[i] && txt[i]<='z'; ++i )
	{ 
		hs4 = hs4 - pt4 * ( txt[i-N] - 'a' ) % mod4 ;
		if ( hs4 < 0 ) hs4 += mod4;
		hs4 = ( hs4 * p4 + txt[i] - 'a' ) % mod4;        
		v[i] = ( v[i] & h4[hs4] );
	}

	for ( i = N ; 'a' <= txt[i] && txt[i]<='z'; ++i )
	{ 
		hs5 = hs5 - pt5 * ( txt[i-N] -'a' ) % mod5 ;
		if ( hs5 < 0 ) hs5 += mod5;
		hs5 = ( hs5 * p5 + txt[i] - 'a' ) % mod5;        
		v[i] = ( v[i] & h5[hs5] );
	}
*/
	for (i=N; 0 <= txt[i] && txt[i] <= 2 ;++i)
		ret+=v[i];

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

	return 0;
}