Pagini recente » Cod sursa (job #2039425) | Cod sursa (job #1411979) | Cod sursa (job #1123245) | Cod sursa (job #1167630) | Cod sursa (job #1098921)
#include<cstdio>
#include<cstring>
int n,m,i,q1,q2,p1,p2,nr1,nr2,nra1,nra2,q,nr,o[2000002];
char a[2000002],b[2000002];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&a);
scanf("%s",&b);
n=strlen(a);
m=strlen(b);
p1=666013;
p2=686969;
q=73;
q1=q2=1;
nr1=nr2=0;
for(i=0;i<n;i++)
{
nra1=(nra1*q+a[i])%p1;
nra2=(nra2*q+a[i])%p2;
if(i>0)
{
q1=(q1*q)%p1,
q2=(q2*q)%p2;
}
}
if(n>m)
{
printf("0\n");
}
else
{
for(i=0;i<n;i++)
{
nr1=(nr1*q+b[i])%p1;
nr2=(nr2*q+b[i])%p2;
}
if(nr1==nra1&&nr2==nra2)
{
o[0]=1;
nr++;
}
for(i=n;i<m;i++)
{
nr1=((nr1-(b[i-n]*q1)%p1+p1)*q+b[i])%p1;
nr2=((nr2-(b[i-n]*q2)%p2+p2)*q+b[i])%p2;
if(nr1==nra1&&nr2==nra2)
{
o[i-n+1]=1;
nr++;
}
}
printf("%d\n",nr);
nr=0;
for(i=0;i<m&&nr<1000;i++)
if (o[i]!=0)
{
nr++;
printf("%d ", i);
}
printf("\n");
}
return 0;
}