Pagini recente » Cod sursa (job #3223222) | Cod sursa (job #2781219) | oji_bv_1112 | Cod sursa (job #2211606) | Cod sursa (job #2623888)
#include <stdio.h>
#include <string.h>
#define MAXL 2000000
#define H1 786433
#define H2 666013
#define BASE 127
char A[MAXL], B[MAXL];
int pos[MAXL], ap;
void verif( int p, int hA1, int hA2, int hB1, int hB2 ) {
if ( hA1 == hB1 && hA2 == hB2 ) {
pos[ap++] = p;
}
}
int main() {
FILE *fin = fopen( "strmatch.in", "r" );
FILE *fout = fopen( "strmatch.out", "w" );
int i, lA, lB, hashA1 = 0, hashA2 = 0, hashB1 = 0, hashB2 = 0, basep1 = 1, basep2 = 1;
fscanf( fin, "%s%s", A, B );
lA = strlen( A );
lB = strlen( B );
for ( i = 0; i < lA; ++i ) {
hashA1 = (A[i] + hashA1 * BASE) % H1;
hashA2 = (A[i] + hashA2 * BASE) % H2;
if ( i != 0 ) {
basep1 = (basep1 * BASE) % H1;
basep2 = (basep2 * BASE) % H2;
}
}
for ( i = 0; i < lA; ++i ) {
hashB1 = (B[i] + hashB1 * BASE) % H1;
hashB2 = (B[i] + hashB2 * BASE) % H2;
}
verif( 0, hashA1, hashA2, hashB1, hashB2 );
for ( i = lA; i < lB; ++i ) {
hashB1 = (((hashB1 - basep1 * B[i - lA] + H1) % H1) * BASE + B[i]) % H1;
hashB2 = (((hashB2 - basep2 * B[i - lA] + H2) % H2) * BASE + B[i]) % H2;
verif( i - lA + 1, hashA1, hashA2, hashB1, hashB2 );
}
fprintf( fout, "%d\n", ap );
for ( i = 0; i < ap; ++i ) {
fprintf( fout, "%d ", pos[i] );
}
fclose( fin );
fclose( fout );
return 0;
}