Pagini recente » Cod sursa (job #2047880) | Cod sursa (job #629419)
Cod sursa(job #629419)
#include <cstdio>
#include <cstring>
#define MaxN 2000005
#define MaxS 1002
const int P = 73, MOD1 = 1000007, MOD2 = 666013;
char A[ MaxN ], B[ MaxN ];
int NA, NB, hashA1, hashA2, hashB1, hashB2, i, P1 = 1, P2 = 1, poz[ MaxS ], nrSol;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", &A, &B);
NA = strlen( A ); NB = strlen( B );
if( NA > NB )
{
printf("0\n");
return 0;
}
for( i = 0; i < NA ; ++i )
{
hashA1 = ( hashA1 * P + A[ i ] ) % MOD1 ;
hashA2 = ( hashA2 * P + A[ i ] ) % MOD2 ;
if( i > 0 )
{
P1 = ( P1 * P ) % MOD1;
P2 = ( P2 * P ) % MOD2;
}
}
for( i = 0; i < NA ; ++i )
{
hashB1 = ( hashB1 * P + B[ i ] ) % MOD1;
hashB2 = ( hashB2 * P + B [ i ] ) % MOD2;
}
if( hashA1 == hashB1 && hashA2 == hashB2 )
poz [ ++ nrSol ] = 0;
for( i = NA ; i < NB ; ++i )
{
hashB1 = ( ( hashB1 - ( B[ i - NA ] * P1 ) % MOD1 + MOD1 ) * P + B[ i ] ) % MOD1;
hashB2 = ( ( hashB2 - ( B[ i - NA ] * P2 ) % MOD2 + MOD2 ) * P + B[ i ] ) % MOD2;
if( hashA1 == hashB1 && hashA2 == hashB2)
{
nrSol ++;
if( nrSol < 1000 )
poz[ nrSol ] = i - NA +1 ;
}
}
printf("%d\n", nrSol);
if( nrSol <= 1000 )
for( i = 1; i <= nrSol ; ++i)
printf( "%d ", poz[ i ] );
else
for( i = 1; i <= 1000 ; ++i)
printf( "%d ", poz[ i ] );
return 0;
}