Pagini recente » Cod sursa (job #1265127) | Cod sursa (job #139083) | Cod sursa (job #349704) | Cod sursa (job #2514116) | Cod sursa (job #300661)
Cod sursa(job #300661)
#include<stdio.h>
#include<string.h>
#define Q 1023
#define Nmax 2000000
char T[Nmax],P[Nmax];
int m,n,b,v[Nmax];
void verif(int k)
{
for(int i=k;i<k+m;++i)
if (T[i]!=P[i-k])
return ;
v[++v[0]]=k;
}
void rabin_karp()
{
int i,p=0,t=0,x=1;
for(i=1;i<m;++i)
x=(x*(b+1)) % Q;
for(i=0;i<m;++i)
{
p=((b+1)*p + P[i]) % Q;
t=((b+1)*t + T[i]) % Q;
}
for(i=0;i+m<=n;++i)
{
if (t==p)
verif(i);
t=(t+Q-(x*T[i])%Q)%Q;
t=((b+1)*t+T[i+m])%Q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",T);
scanf("%s",P);
m=strlen(P),n=strlen(T),b=10;
rabin_karp();
printf("%d\n",v[0]);
for(int i=1;i<=v[0];++i)
printf("%d ",v[i]);
return 0;
}