Pagini recente » Cod sursa (job #498991) | Cod sursa (job #2700220) | Cod sursa (job #2957268) | Cod sursa (job #3210209) | Cod sursa (job #709601)
Cod sursa(job #709601)
#include<stdio.h>
#include<string.h>
#define mod1 1000013
#define mod2 1000029
#define baza 79
char a[2000010],b[2000010];
int n,m,i,j,v[2000000];
unsigned ha1,ha2,hb1,hb2,p1,p2;
int main()
{freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",a,b);
n=strlen(a)-1;
m=strlen(b)-1;
if(n>m)
{printf("0");
return 0;
}
for(i=0;i<=1000;i++)
v[i]=-1;
p1=p2=1;
for(i=0;i<n;i++)
{ha1=(ha1*baza+a[i])%mod1;
ha2=(ha2*baza+a[i])%mod2;
hb1=(hb1*baza+b[i])%mod1;
hb2=(hb2*baza+b[i])%mod2;
if(!i)
continue;
p1=(p1*baza)%mod1;
p2=(p2*baza)%mod2;
}
for(i=0,j=1;i<m-n;i++)
{if(ha1==hb1&&ha2==hb2)
{v[0]++;
v[j++]=i;
}
hb1=((hb1-(b[i]*p1)%mod1+mod1)*baza+b[i+n])%mod1;
hb2=((hb2-(b[i]*p2)%mod2+mod2)*baza+b[i+n])%mod2;
}
printf("%d\n",++v[0]);
for(i=1;(i<=1000)&&(v[i]!=-1);i++)
printf("%d ",v[i]);
fclose(stdin);
fclose(stdout);
return 0;
}