Pagini recente » Cod sursa (job #2014255) | Cod sursa (job #3150397) | Profil Crimz0n25 | Cod sursa (job #1447079) | Cod sursa (job #153208)
Cod sursa(job #153208)
#include <stdio.h>
#include <string.h>
#define NMAX 2000001
#define p 97
#define mod1 100007
#define mod2 100027
int match[NMAX];
int main()
{ freopen("strmatch.in","rt",stdin);
freopen("strmatch.out","wt",stdout);
char a[NMAX],b[NMAX];
long na,nb,hash1,hash2,cod1,cod2,p1,p2;
scanf("%s %s",a,b);
long i;
p1=1;
p2=1;
cod1=0;
cod2=0;
na=strlen(a);
nb=strlen(b);
if (na>nb)
{ printf("0");
return 0;
}
for (i=0;i<na;i++)
{ cod1=(cod1*p+a[i])%mod1;
cod2=(cod2*p+a[i])%mod2;
if (i)
{ p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
hash1=hash2=0;
for (i=0;i<na;i++)
{ hash1=(hash1*p+b[i])%mod1;
hash2=(hash2*p+b[i])%mod2;
}
long nr=0;
if (cod1==hash1&&cod2==hash2)
{ match[0]=1;
nr++;
}
for (i=na;i<nb;i++)
{ hash1=((hash1-(b[i-na]*p1))*p+b[i])%mod1;
hash2=((hash2-(b[i-na]*p2))*p+b[i])%mod2;
if (hash1==cod1&&hash2==cod2)
{ nr++;
match[i-na+1]=1;
}
}
printf("%ld\n",nr);
nr=0;
i=0;
while (i<nb&&nr<1000)
{ if (match[i]==1)
{ printf("%ld ",i);
nr++;
}
i++;
}
fclose(stdin);
fclose(stdout);
return 0;
}