Pagini recente » Cod sursa (job #357396) | Cod sursa (job #2455495) | Cod sursa (job #1694084) | Cod sursa (job #129663) | Cod sursa (job #496682)
Cod sursa(job #496682)
#include <stdio.h>
#include <string.h>
int M1,M2,B,cod1,cod2,sir1,sir2,n,m,i,pow1,pow2,sol,ok[300],v[2000002];
char a[2000002],b[2000002];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
n=strlen(a)-1;
if(a[n]=='\n') n--;
m=strlen(b)-1;
if(b[m]=='\n') m--;
sir1=0;
cod1=0;
sir2=0;
cod2=0;
B=0;
M1=999983;
M2=999961;
B=97;
for(i=0;i<=n;i++)
{
sir1=(sir1*B+a[i])%M1;
sir2=(sir2*B+a[i])%M2;
}
for(i=0;i<=n;i++)
{
cod1=(cod1*B+b[i])%M1;
cod2=(cod2*B+b[i])%M2;
}
pow1=1;
pow2=1;
for(i=0;i<n;i++)
{
pow1=(pow1*B)%M1;
pow2=(pow2*B)%M2;
}
sol=0;
if(cod1==sir1&&cod2==sir2)
{
sol++;
v[0]=1;
}
for(i=n+1;i<=m;i++)
{
cod1=(cod1+M1-(b[i-n-1]*pow1)%M1)%M1;
cod1=(cod1*B+b[i])%M1;
cod2=(cod2+M2-(b[i-n-1]*pow2)%M2)%M2;
cod2=(cod2*B+b[i])%M2;
if(cod1==sir1&&cod2==sir2)
{
sol++;
v[i-n]=1;
}
}
printf("%d\n",sol);
sol=1;
i=0;
while(sol<=1000&&i<=m)
{
if(v[i])
{
printf("%d ",i);
sol++;
}
i++;
}
printf("\n");
return 0;
}