Pagini recente » Cod sursa (job #1316709) | Cod sursa (job #1820777) | Cod sursa (job #3190013) | Clasamentul arhivei educationale | Cod sursa (job #428278)
Cod sursa(job #428278)
#include<stdio.h>
#include<string.h>
#define p 73
#define m1 100003
#define m2 100019
#define Nmax 2000010
char a[Nmax],b[Nmax];
int n1,n2,ha1,ha2,hb1,hb2,pmax1,pmax2,nr,sol[1005];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
n1=strlen(a);
n2=strlen(b);
if(n1>n2) {printf("0\n");return 0;}
pmax1=pmax2=1;
int i;
for(i=0;i<n1;i++)
{
ha1=(ha1*p+a[i])%m1;
ha2=(ha2*p+a[i])%m2;
hb1=(hb1*p+b[i])%m1;
hb2=(hb2*p+b[i])%m2;
if(i!=0)
{
pmax1=(pmax1*p)%m1;
pmax2=(pmax2*p)%m2;
}
}
if(ha1==hb1 && ha2==hb2)
sol[nr++]=0;
for(i=n1;i<n2;i++)
{
hb1=((hb1-(b[i-n1]*pmax1)%m1+m1)*p+b[i])%m1;
hb2=((hb2-(b[i-n1]*pmax2)%m2+m2)*p+b[i])%m2;
if(ha1==hb1 && ha2==hb2)
sol[nr++]=i-n1+1;
if(nr==1000)
break;
}
printf("%d\n",nr);
for(i=0;i<nr;i++)
printf("%d ",sol[i]);
return 0;
}