Pagini recente » Cod sursa (job #2712740) | Cod sursa (job #2014108) | Cod sursa (job #264219) | Cod sursa (job #304218) | Cod sursa (job #428718)
Cod sursa(job #428718)
#include<stdio.h>
#include<string.h>
#define p1 41 // pentru primul hash
#define p2 101 // pentru al doilea hash
#define Nmax 2000010
char a[Nmax],b[Nmax];
int n1,n2,ha1,ha2,hb1,hb2,pmax1,pmax2,nr,sol[Nmax];
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*p1+a[i];
ha2=ha2*p2+a[i];
hb1=hb1*p1+b[i];
hb2=hb2*p2+b[i];
if(i!=0)
{
pmax1=pmax1*p1;
pmax2=pmax2*p2;
}
}
if(ha1==hb1 && ha2==hb2)
sol[nr++]=0;
for(i=n1;i<n2;i++)
{
hb1=(hb1-(b[i-n1]*pmax1))*p1+b[i];
hb2=(hb2-(b[i-n1]*pmax2))*p2+b[i];
if(ha1==hb1 && ha2==hb2)
sol[nr++]=i-n1+1;
}
printf("%d\n",nr);
for(i=0;i<nr && i<1000;i++)
printf("%d ",sol[i]);
return 0;
}