Pagini recente » Cod sursa (job #3282072) | Cod sursa (job #1902183) | Cod sursa (job #2926151) | Cod sursa (job #3224736) | Cod sursa (job #2623970)
#include <stdio.h>
#include <string.h>
#define MAXL 2000000
#define H1 32103110
#define H2 666013
#define BASE 62
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;
}
}
unsigned cod(char ch) {
if ('a' <= ch && ch <= 'z') {
return ch - 'a';
}
if ('A' <= ch && ch <= 'Z') {
return ch - 'A' + 26;
}
return ch - '0' + 52;
}
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 = (cod(A[i]) + hashA1 * BASE) % H1;
hashA2 = (cod(A[i]) + hashA2 * BASE) % H2;
if ( i != 0 ) {
basep1 = (basep1 * BASE) % H1;
basep2 = (basep2 * BASE) % H2;
}
}
for ( i = 0; i < lA; ++i ) {
hashB1 = (cod(B[i]) + hashB1 * BASE) % H1;
hashB2 = (cod(B[i]) + hashB2 * BASE) % H2;
}
verif( 0, hashA1, hashA2, hashB1, hashB2 );
for ( i = lA; i < lB; ++i ) {
hashB1 = (((hashB1 + H1 - (basep1 * cod(B[i - lA])) % H1) % H1) * BASE + cod(B[i])) % H1;
hashB2 = (((hashB2 + H2 - (basep2 * cod(B[i - lA])) % H2) % H2) * BASE + cod(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;
}