Pagini recente » Cod sursa (job #1969355) | Cod sursa (job #609332) | Cod sursa (job #409313) | Cod sursa (job #2500292) | Cod sursa (job #1429230)
/*
Worg
*/
#include <cstdio>
#include <vector>
#include <cstring>
#define MOD 1000003
#define MOD_2 666013
#define DIM 10000010
#define sigma 5
using namespace std;
FILE *fin = freopen("abc2.in","r",stdin);
FILE *fout = freopen("abc2.out","w",stdout);
vector <int> Hash[ MOD ], viz[ MOD ];
char T[ DIM ], F[ 30 ];
int len_1, len_2, rest_1, rest_2, x1, x2;
inline int val( char x )
{
int ret = x - 'a';
return ret;
}
void Read()
{
gets( T ); gets( F );
len_1 = strlen( T ), len_2 = strlen( F );
rest_1 = sigma, rest_2 = sigma;
for(int i = 2; i <= len_2; ++i)
{
rest_1 = (rest_1 * sigma) % MOD;
rest_2 = (rest_2 * sigma) % MOD_2;
}
}
inline void giveValues()
{
x1 = 0, x2 = 0;
for(int i = 0; i < len_2; ++i)
{
x1 = (x1 * sigma + val( F[i] )) % MOD;
x2 = (x2 * sigma + val( F[i] )) % MOD_2;
}
}
inline bool Find()
{
for(int i = 0; i < viz[x1].size(); ++i)
if( viz[x1][i] == x2 )
return 1;
return 0;
}
void Set()
{
int i, nr = 0, nr_2 = 0;
for(i = 0; i < len_2; ++i)
{
nr = ( nr * sigma + val( T[i] ) ) % MOD;
nr_2 = ( nr_2 * sigma + val( T[i] ) ) % MOD_2;
}
Hash[ nr ].push_back( nr_2 );
for(i = len_2; i < len_1; ++i)
{
nr = (nr * sigma + val( T[i] ) ) % MOD;
nr_2 = ( nr_2 * sigma + val( T[i] ) ) % MOD_2;
nr -= rest_1 * val( T[i - len_2] );
nr_2 -= rest_2 * val( T[i - len_2] );
while(nr < 0)
nr += MOD;
while(nr_2 < 0)
nr_2 += MOD_2;
Hash[ nr ].push_back( nr_2 );
}
}
void Solve()
{
int i, j, ans = 0;
giveValues();
for(i = 0; i < Hash[x1].size(); ++i)
{
ans += ( Hash[x1][i] == x2 );
}
while( gets(F) )
{
giveValues();
if( Find() )
continue;
for(i = 0; i < Hash[x1].size(); ++i)
{
ans += ( Hash[x1][i] == x2 );
}
viz[x1].push_back( x2 );
}
printf("%d", ans);
}
int main()
{
Read();
if( len_2 > len_1 )
{
printf("0");
return 0;
}
Set();
Solve();
return 0;
}