Pagini recente » Cod sursa (job #2146639) | Cod sursa (job #597161) | Cod sursa (job #1794812) | Cod sursa (job #456956) | Cod sursa (job #147366)
Cod sursa(job #147366)
#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, kM=0, kS=0,kM2=0, kS2=0, lenS, lenM, i, K=1, K2=1, flag, j;
lenS=strlen(S);
lenM=strlen(M);
for (i=0; i<lenM; i++)
{
K*=b; K2*=b;
K%=MOD; K2%=MOD2;
kM*=b; kM2*=b;
kM+=M[i]; kM2+=M[i];
kM%=MOD; kM2%=MOD2;
kS*=b; kS2*=b;
kS+=S[i]; kS2+=S[i];
kS%=MOD; kS2%=MOD2;
}
if ((kS2==kM2)&&(kS2==kM2))
{
flag=1;
for (j=0; j<lenM; j++)
{
if (M[j]!=S[j])
{
flag=0;
break;
}
}
if (flag)
{
++r;
sol[r]=0;
}
}
// printf("%d %d %d %d %d %d\n", kM, kS, kM2, kS2, kM3, kS3);
for (; i<lenS; i++)
{
kS*=b; kS2*=b;
kS-=(S[i-lenM]*K)%MOD;
kS2-=(S[i-lenM]*K2)%MOD2;
kS+=S[i]; kS2+=S[i];
kS%=MOD; kS2%=MOD2;
if ((kS==kM)&&(kS2==kM2))
{
flag=1;
for (j=0; j<lenM; j++)
{
if (M[j]!=S[j+(i-lenM+1)])
{
flag=0;
break;
}
}
if (flag)
{
++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, 20347, 23917);
printf("%d\n", r);
for (i=1; i<=r && i<=1000; i++)
{
printf("%d ", sol[i]);
}
fclose(stdout);
return 0;
}