Pagini recente » Istoria paginii runda/baraj2_lasm_cl11-12 | Istoria paginii utilizator/alexfocu | Istoria paginii utilizator/star1star21 | Istoria paginii utilizator/mara_sarbu | Cod sursa (job #103498)
Cod sursa(job #103498)
#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];
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);
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));
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] ) ;
memset(v,1,sizeof(v));
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 + txt[i] - 'a' ) % 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; 'a' <= txt[i] && txt[i] <= 'z' ;++i)
ret+=v[i];
printf("%d\n",ret);
return 0;
}