Pagini recente » Cod sursa (job #1400835) | Cod sursa (job #2897809) | Cod sursa (job #1619627) | Cod sursa (job #1643085) | Cod sursa (job #102358)
Cod sursa(job #102358)
#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];
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 )
{
txt[i]-='a';
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] ) ;
for ( i = N ; 'a' <= txt[i] && txt[i]<='z'; ++i )
{
txt[i]-='a';
hs1 = hs1 - pt1 * txt[i-N] % mod1 ;
if ( hs1 < 0 ) hs1 += mod1;
hs1 = hs1 * p1 % mod1 + txt[i];
if ( hs1 >= mod1 )
hs1-=mod1;
hs2 = hs2 - pt2 * txt[i-N] % mod2 ;
if ( hs2 < 0 ) hs2 += mod2;
hs2 = hs2 * p2 + txt[i];
if ( hs2 >= mod2 )
hs2-=mod2;
hs3 = hs3 - pt3 * txt[i-N] % mod3 ;
if ( hs3 < 0 ) hs3 += mod3;
hs3 = ( hs3 * p3 + txt[i] );
if ( hs3 >= mod3 )
hs3-=mod3;
hs4 = hs4 - pt4 * txt[i-N] % mod4 ;
if ( hs4 < 0 ) hs4 += mod4;
hs4 = hs4 * p4 + txt[i];
if ( hs4 >= mod4 )
hs4-=mod4;
hs5 = hs5 - pt5 * txt[i-N] % mod5 ;
if ( hs5 < 0 ) hs5 += mod5;
hs5 = hs5 * p5 + txt[i];
if ( hs5 >= mod5 )
hs5-=mod5;
ret = ret + ( h1[hs1] & h2[hs2] & h3[hs3] & h4[hs4] & h5[hs5] ) ;
}
printf("%d\n",ret);
return 0;
}