Pagini recente » Cod sursa (job #2980320) | Cod sursa (job #928808) | Cod sursa (job #1016429) | Cod sursa (job #3152536) | Cod sursa (job #1514675)
#include<cstdio>
#include<cstring>
#define n1 2000003
#define n2 2000017
char v[2000001],v2[2000001],sol[1001];
int main ()
{freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
int k1,k2,i,m1,m2,p1,p2,x1,x2,q=0;
scanf("%s%s",&v,&v2);
k1=strlen(v);
k2=strlen(v2);
x1=x2=1;
m1=0;
m2=0;
for(i=k1-1;i>=0;i--)
{m1=(m1+v[i]*x1)%n1;
m2=(m2+v[i]*x2)%n2;
x1=(x1*123)%n1;
x2=(x2*123)%n2;
}
x1=x2=1;
p1=0;
p2=0;
for(i=k1-1;i>=0;i--)
{p1=(p1+v2[i]*x1)%n1;
p2=(p2+v2[i]*x2)%n2;
x1=(x1*123)%n1;
x2=(x2*123)%n2;
}
x1=(x1/123)%n1;
x2=(x2/123)%n2;
if(m1==p1&&m2==p2)
{q=1;
sol[1]=0;
}
for(i=1;i<k2-k1+1;i++)
{p1=(p1-v2[i-1]*x1+n1)%n1;
p2=(p2-v2[i-1]*x2+n2)%n2;
p1=(p1*123)%n1;
p2=(p2*123)%n2;
p1=(p1+v2[i+k1-1])%n1;
p2=(p2+v2[i+k1-1])%n2;
if(m1==p1&&m2==p2)
{q++;
if(q<=1000)
sol[q]=i;
}
}
printf("%d\n",q);
for(i=1;i<=q;i++)
printf("%d ",sol[i]);
return 0;
}