Pagini recente » Cod sursa (job #1684340) | Cod sursa (job #386540) | Cod sursa (job #1962056) | Cod sursa (job #1751714) | Cod sursa (job #496684)
Cod sursa(job #496684)
#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()
{
FILE *f,*g;
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fgets(a,2000002,f);
fgets(b,2000002,f);
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=100007;
M2=100021;
B=73;
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;
}
}
fprintf(g,"%d\n",sol);
sol=1;
i=0;
while(sol<=1000&&i<=m)
{
if(v[i])
{
fprintf(g,"%d ",i);
sol++;
}
i++;
}
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}