Cod sursa(job #236707)
#include<stdio.h>
#include<string.h>
#define NMAX 2000001
#define baza 73
#define mod1 1000007
#define mod2 1000023
char a[NMAX],b[NMAX];
long n,m,hasha1,hasha2,hashb1,hashb2,lung;
int viz[NMAX];
int main()
{
long i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a);
scanf("%s",b);
m=strlen(a);
n=strlen(b);
hasha1=hasha2=hashb1=hashb2=0;
long d1,d2;
d1=d2=1;
for(i=0;i<m;i++)
{
hasha1=(hasha1*baza+a[i])%mod1;
hasha2=(hasha2*baza+a[i])%mod2;
hashb1=(hashb1*baza+b[i])%mod1;
hashb2=(hashb2*baza+b[i])%mod2;
if(i!=0)
{
d1=(d1*baza)%mod1;
d2=(d2*baza)%mod2;
}
}
if(hasha1==hashb1&&hasha2==hashb2)
{viz[0]=1;
lung++;
}
for(i=1;i<=n-m+1;i++)
{
hashb1=((hashb1-(b[i-1]*d1)%mod1+mod1)*baza+b[i+m-1])%mod1;
hashb2=((hashb2-(b[i-1]*d2)%mod2+mod2)*baza+b[i+m-1])%mod2;
if(hasha1==hashb1&&hasha2==hashb2)
{
lung++;viz[i]=1;
}
}
printf("%ld\n",lung);
int contor=1;
for(i=0;i<n&&contor<=1000;i++)
if(viz[i]==1)
{
printf("%ld ",i);
contor++;
}
return 0;
}