Pagini recente » Cod sursa (job #1947210) | Cod sursa (job #2175524) | Cod sursa (job #429726) | Cod sursa (job #2258281) | Cod sursa (job #2623966)
#include <stdio.h>
#include <string.h>
#define MAXL 2000000
#define H1 32103110
#define H2 666013
#define BASE 123
char A[MAXL], B[MAXL];
int pos[MAXL], ap;
static inline void verif( unsigned p, unsigned hA1, unsigned hA2, unsigned hB1, unsigned 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;
unsigned 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 + H1 - (basep1 * B[i - lA]) % H1) % H1) * BASE + B[i]) % H1;
hashB2 = (((hashB2 + H2 - (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;
}