Pagini recente » Cod sursa (job #2447391) | Cod sursa (job #2814176) | Cod sursa (job #1892200) | Cod sursa (job #528164) | Cod sursa (job #1076047)
#include<stdio.h>
#include<string.h>
char A[2000001], B[2000001];
int sol[1024];
int rabin_karp(char *S, char *M,int b, int MOD, int MOD2){
int r=0, kM1=M[0], kS1=S[0],kM2=M[0], kS2=S[0], lenS, lenM, i, P1=1, P2=1;
lenS=strlen(S);
lenM=strlen(M);
for (i=1; i<lenM; i++){
kM1=(kM1*b+M[i])%MOD;
kM2=(kM2*b+M[i])%MOD2;
kS1=(kS1*b+S[i])%MOD;
kS2=(kS2*b+S[i])%MOD2;
P1=(P1*b)%MOD;
P2=(P2*b)%MOD2;
}
if ((kM1==kS1)&&(kM2==kS2)){
++r;
sol[r]=0;
}
for (i=lenM; i<lenS; i++){
kS1=((kS1- (S[i-lenM]*P1)%MOD + MOD ) *b+S[i])%MOD;
kS2=((kS2- (S[i-lenM]*P2)%MOD2+ MOD2) *b+S[i])%MOD2;
if ((kM1==kS1)&&(kM2==kS2))
{
++r;
if (r<=1001)
sol[r]=i-lenM+1;
}
}
return r;
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(A);
gets(B);
int r,i;
r=rabin_karp(B, A, 128, 100007, 100021);
printf("%d\n", r);
for (i=1;i<=r && i<=1000;i++){
printf("%d ", sol[i]);
}
fclose(stdout);
return 0;
}