Pagini recente » Cod sursa (job #307050) | Cod sursa (job #2854257) | Cod sursa (job #2210466) | Cod sursa (job #2227631) | Cod sursa (job #102334)
Cod sursa(job #102334)
#include <cstdio>
#include <iostream>
using namespace std;
#define fin "abc2.in"
#define fout "abc2.out"
const int mod1 = 75371;
const int mod2 = 95657;
const int mod3 = 83121;
const int mod4 = 63473;
const int mod5 = 77243;
const int p1 = 5, p2 = 7, p3 = 19, p4 = 31, p5 = 53;
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 ) % mod1;
hs2 = ( hs2 + ( txt[i] - 'a' ) * pt2 % mod2 ) % mod2;
hs3 = ( hs3 + ( txt[i] - 'a' ) * pt3 % mod3 ) % mod3;
hs4 = ( hs4 + ( txt[i] - 'a' ) * pt4 % mod4 ) % mod4;
hs5 = ( hs5 + ( txt[i] - 'a' ) * pt5 % mod5 ) % 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);
if ( h1[hs1] && h2[hs2] && h3[hs3] && h4[hs4] && h5[hs5] )
++ret;
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;
hs1 = ( hs1 + txt[i] - 'a' ) % mod1;
hs2 = hs2 - pt2 * ( txt[i-N] - 'a' ) % mod2;
if ( hs2 < 0 ) hs2 += mod2;
hs2 = ( hs2 * p2 ) % mod2;
hs2 = ( hs2 + txt[i] - 'a' ) % mod2;
hs3 = hs3 - pt3 * ( txt[i-N] - 'a' ) % mod3;
if ( hs3 < 0 ) hs3 += mod3;
hs3 = ( hs3 * p3 ) % mod3;
hs3 = ( hs3 + txt[i] - 'a' ) % mod3;
hs4 = hs4 - pt4 * ( txt[i-N] - 'a' ) % mod4;
if ( hs4 < 0 ) hs4 += mod4;
hs4 = ( hs4 * p4 ) % mod4;
hs4 = ( hs4 + txt[i] - 'a' ) % mod4;
hs5 = hs5 - pt5 * ( txt[i-N] - 'a' ) % mod5;
if ( hs5 < 0 ) hs5 += mod5;
hs5 = ( hs5 * p5 ) % mod5;
hs5 = ( hs5 + txt[i] - 'a' ) % mod5;
if ( h1[hs1] && h2[hs2] && h3[hs3] && h4[hs4] && h5[hs5] )
++ret;
}
printf("%d\n",ret);
return 0;
}