Pagini recente » Cod sursa (job #247632) | Cod sursa (job #379949) | Cod sursa (job #1233145) | Cod sursa (job #173505) | Cod sursa (job #496659)
Cod sursa(job #496659)
#include <stdio.h>
#include <string.h>
long M1,M2,B,cod1,cod2,sir1,sir2,n,m,i,pow1,pow2,sol,v[1002],ok[255];
char a[2000002],b[2000002];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,2000002,stdin);
fgets(b,2000002,stdin);
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;
for(i=0;i<=n;i++)
if(ok[a[i]]==0)
{
B++;
ok[a[i]]=1;
}
for(i=0;i<=m;i++)
if(ok[b[i]]==0)
{
B++;
ok[b[i]]=1;
}
B++;
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++;
if(sol<=1000) v[sol]=0;
}
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++;
}
}
printf("%ld\n",sol);
if(sol>1000) sol=1000;
for(i=1;i<=sol;i++)
printf("%ld ",v[i]);
printf("\n");
return 0;
}