Pagini recente » Cod sursa (job #1392274) | Cod sursa (job #1447938) | Cod sursa (job #927086) | Cod sursa (job #393939) | Cod sursa (job #98648)
Cod sursa(job #98648)
#include <cstdio>
#include <cstring>
#define H_SIZE 2789327
#define NR_H 2
int N, M, L, ret, ok;
char A[10111111], cuv[50111][22];
unsigned short hash[NR_H][H_SIZE];
int base[4] = { 101, 207, 413, 593 }, po[4][22], HS[4] = { 2455001, 2677013, 2124017, 2129023 };
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
int i, j, l, k;
unsigned int at[4], val;
val = at[0] = at[1] = at[2] = at[3] = 0;
gets( A );
L = strlen( A );
while( gets( cuv[++N] ) );
--N;
if( N == 0 )
{
printf("0\n");
return 0;
}
M = strlen(cuv[1]);
if( M > L )
{
printf("0\n");
return 0;
}
for( l = 0; l < L; l++ )
A[l] -= 'a';
for( i = 1; i <= N; i++ )
for( l = 0; l < M; l++ )
cuv[i][l] -= 'a';
for( j = 0; j < NR_H; j++ )
{
po[j][0] = 1;
for( i = 1; i <= M; i++ )
po[j][i] = ( (long long)( po[j][i-1] ) * base[j] ) % HS[j];
}
for( i = 1; i <= N; i++ )
for( j = 0; j < NR_H; j++ )
{
val = 0;
for( k = 0; k < M; k++ )
val += po[j][M-k-1] * (int)cuv[i][k];
val %= HS[j];
hash[ j ][ val ] = i;
}
for( l = 0; l < L; l++ )
{
for( j = 0; j < NR_H; j++ )
{
if( l < M ) at[j] += po[j][M-l-1] * (int)A[l], at[j] %= HS[j];
else
{
at[j] = ( base[j] * ( ( 2 * HS[j]+ at[j] - po[j][M-1] * A[ l - M ] ) % HS[j] ) ) % HS[j] + (int)(A[l]),
at[j] %= HS[j];
}
}
if( l >= M - 1 )
{
ok = 1;
for( i = 0; ok && i < NR_H; i++ )
if( !hash[ i ][ at[i] ] || hash[ i ][ at[i] ] != hash[ 0 ][ at[0] ] )
ok = 0;
if( ok )
ret++;
}
}
printf("%d\n", ret);
return 0;
}