Pagini recente » Borderou de evaluare (job #72616) | Borderou de evaluare (job #2020897) | Borderou de evaluare (job #2008545) | Cod sursa (job #920776) | Cod sursa (job #428276)
Cod sursa(job #428276)
#include<stdio.h>
#include<string.h>
#define p 101
#define m1 996067
#define m2 999983
#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)*p+b[i])%m1;
hb2=((hb2-b[i-n1]*pmax2)*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;
}