Pagini recente » Cod sursa (job #694029) | Cod sursa (job #52207) | Cod sursa (job #1385479) | Cod sursa (job #1900859) | Cod sursa (job #1583451)
#include <cstdio>
#include <cstring>
const int VAL1 = 23;
const int VAL2 = 29;
const int MOD1 = 100007;
const int MOD2 = 100021;
const int DIM = 1 << 21;
const int DIM2 = 1 << 10;
int N, M, K; char A[DIM], B[DIM];
int hash1, hash2, exp1 = 1, exp2 = 1;
int value1, value2, Answer[DIM2];
int main () {
freopen( "strmatch.in" , "r", stdin );
freopen( "strmatch.out", "w", stdout );
scanf( "%s %s", A, B );
N = strlen( A );
M = strlen( B );
for( int i = 0; i < N; i ++ ) {
hash1 = (hash1 * VAL1 + A[i]) % MOD1;
hash2 = (hash2 * VAL2 + A[i]) % MOD2;
if( i ) {
exp1 = (exp1 * VAL1) % MOD1;
exp2 = (exp2 * VAL2) % MOD2;
}
}
if( N > M ) {
printf( "0\n" );
return 0;
}
for( int i = 0; i < N; i ++ ) {
value1 = (value1 * VAL1 + B[i]) % MOD1;
value2 = (value2 * VAL2 + B[i]) % MOD2;
}
if( value1 == hash1 && value2 == hash2 )
Answer[++K] = 0;
for( int i = N; i < M; i ++ ) {
value1 = ((value1 - (B[i - N] * exp1) % MOD1 + MOD1) * VAL1 + B[i]) % MOD1;
value2 = ((value2 - (B[i - N] * exp2) % MOD2 + MOD2) * VAL2 + B[i]) % MOD2;
if( value1 == hash1 && value2 == hash2 ) {
K ++;
if( K <= 1000 )
Answer[K] = i - N + 1;
}
}
printf( "%d\n", K );
for( int i = 1; i <= K && i <= 1000; i ++ )
printf( "%d ", Answer[i] );
return 0;
}