Cod sursa(job #102341)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 14 noiembrie 2007 12:01:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 3.01 kb
#include <cstdio>
#include <iostream>

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,h1[mod1],h2[mod2],h3[mod3],h4[mod4],h5[mod5];
char buff[Nmax];
char txt[Mmax];

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;

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

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

	while ( 'a' <= buff[N] && buff[N] <= 'z' ) ++ 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] - 'a' ) * pt1 ) % mod1;
		hs2 = ( hs2 + ( txt[i] - 'a' ) * pt2 ) % mod2;
		hs3 = ( hs3 + ( txt[i] - 'a' ) * pt3 ) % mod3;
		hs4 = ( hs4 + ( txt[i] - 'a' ) * pt4 ) % mod4;
		hs5 = ( hs5 + ( txt[i] - 'a' ) * 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] ) ; 

	for ( i = N ; 'a' <= txt[i] && txt[i]<='z'; ++i )
	{
		hs1 = hs1 - pt1 * ( txt[i-N] - 'a' ) % mod1 ;
		if ( hs1 < 0 ) hs1 += mod1;
		hs1 = ( hs1 * p1 % mod1 + txt[i] - 'a' ) % mod1; 

		hs2 = hs2 - pt2 * ( txt[i-N] - 'a' ) % mod2 ;
		if ( hs2 < 0 ) hs2 += mod2;
		hs2 = ( hs2 * p2 + txt[i] - 'a' ) % mod2; 

        hs3 = hs3 - pt3 * ( txt[i-N] - 'a' ) % mod3 ;
		if ( hs3 < 0 ) hs3 += mod3;
		hs3 = ( hs3 * p3 + txt[i] - 'a' ) % mod3; 

        hs4 = hs4 - pt4 * ( txt[i-N] - 'a' ) % mod4 ;
		if ( hs4 < 0 ) hs4 += mod4;
		hs4 = ( hs4 * p4 + txt[i] - 'a' ) % mod4; 

        hs5 = hs5 - pt5 * ( txt[i-N] - 'a' ) % mod5 ;
		if ( hs5 < 0 ) hs5 += mod5;
		hs5 = ( hs5 * p5 + txt[i] - 'a' ) % mod5; 
    
        ret = ret + ( h1[hs1] & h2[hs2] & h3[hs3] & h4[hs4] & h5[hs5] ) ; 
    
    }

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

	return 0;
}