Pagini recente » Cod sursa (job #642340) | Cod sursa (job #2986235) | Cod sursa (job #2234141) | Cod sursa (job #2455463) | Cod sursa (job #155028)
Cod sursa(job #155028)
#include<stdio.h>
#include<string.h>
#define B 73
#define mod1 100021
#define mod2 100007
long n1,n2,m1,m2,i,p1,p2,la,lb,nr;
long sol[1000];
char a[2000000],b[2000000];
int main(void)
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",a,b);
p1=1;
p2=1;
la=strlen(a);
lb=strlen(b);
for(i=0;i<la;i++)
{
n1=(n1*B+a[i])%mod1;
n2=(n2*B+a[i])%mod2;
if(i)
{
p1*=B;
p2*=B;
}
}
if(la>lb)
return 0;
for(i=0;i<la;i++)
{
m1=(m1*B+b[i])%mod1;
m2=(m2*B+b[i])%mod2;
}
if(m1==n1&&m2==n2)
sol[++nr]=0;
for(i=la;i<lb;i++)
{
m1=((m1-(b[i-la]*p1)%mod1+mod1)*B+b[i])%mod1;
m2=((m2-(b[i-la]*p2)%mod2+mod2)*B+b[i])%mod2;
if(m1==n1&&m2==n2)
{
nr++;
if(nr<=1000)
sol[nr]=i-la+1;
}
}
printf("%d\n",nr);
for(i=1;i<=nr;i++)
printf("%d ",sol[i]);
printf("\n");
return 0;
}