Pagini recente » Cod sursa (job #2547870) | Cod sursa (job #584620) | Cod sursa (job #1377016) | Cod sursa (job #1389880) | Cod sursa (job #524894)
Cod sursa(job #524894)
#include<stdio.h>
#include<stdlib.h>
#include<string>
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int N,M,sir[1005],Nr,bz,i;
unsigned int HA1,HB1,P1;
unsigned char HA2,HB2,P2;
char A[2000005],B[2000005];
int main () {
fscanf(f,"%s",A);
fscanf(f,"%s",B);
N = strlen(A); M = strlen(B); bz = 73;
if ( N > M ){
fprintf(g,"%d\n",0);
fclose(f); fclose(g); exit(0);
}
for ( i = 0 ; i < N ; ++i ){
HA1 = HA1 * bz + A[i];
HA2 = HA2 * bz + A[i];
HB1 = HB1 * bz + B[i];
HB2 = HB2 * bz + B[i];
}
P1 = P2 = 1;
for ( i = 1 ; i < N ; ++i ){
P1 = P1 * bz ;
P2 = P2 * bz ;
}
if ( HA1 == HB1 && HA2 == HB2 ){
sir[++Nr] = 0;
}
for ( i = N ; i < M ; ++i ){
HB1 = HB1 - B[ i - N ] * P1;
HB1 = HB1 * bz + B[i];
HB2 = HB2 - B[ i - N ] * P2;
HB2 = HB2 * bz + B[i];
if ( HA1 == HB1 && HA2 == HB2 ){
++Nr;
if ( Nr <= 1000 )
sir[Nr] = i - N + 1;
}
}
fprintf(g,"%d\n",Nr);
for ( i = 1 ; i <= Nr ; ++i )
fprintf(g,"%d ",sir[i]);
fclose(f);
fclose(g);
return 0;
}