Pagini recente » Cod sursa (job #877126) | Cod sursa (job #1691411) | Cod sursa (job #617390) | Cod sursa (job #412383) | Cod sursa (job #147421)
Cod sursa(job #147421)
#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;
}
//printf("%d %d %d %d\n", kM1, kS1, kM2, kS2);
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;
// printf("%d %d %d %d\n", kM1, kS1, kM2, kS2);
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;
}