Pagini recente » Cod sursa (job #2174844) | Cod sursa (job #1806508) | Cod sursa (job #2866397) | Cod sursa (job #2406587) | Cod sursa (job #312413)
Cod sursa(job #312413)
#include <stdio.h>
#include <string.h>
#define dim 2000010
#define p 73
#define mod1 100007
#define mod2 100021
char a[dim], b[dim], match[dim];
int hasha1, hasha2, hash1, hash2, na, nb, ct=0, p1, p2;
int main()
{
int i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s\n", a, b);
na=strlen(a);
nb=strlen(b);
hasha1=hasha2=0;
p1=p2=1;
for (i=0; i<na; i++)
{
hasha1=(hasha1*p+a[i])%mod1;
hasha2=(hasha2*p+a[i])%mod2;
if (i!=0)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
if (na>nb)
{
printf("0\n");
return 0;
}
hash1=hash2=0;
for (i=0; i<na; i++)
{
hash1=(hash1*p+b[i])%mod1;
hash2=(hash2*p+b[i])%mod2;
}
if (hash1==hasha1 && hash2==hasha2)
{
match[0]=1;
ct++;
}
for (i=na; i<nb; i++)
{
hash1=((hash1-(b[i-na]*p1)%mod1+mod1)*p+b[i])%mod1;
hash2=((hash2-(b[i-na]*p2)%mod2+mod2)*p+b[i])%mod2;
if (hash1==hasha1 && hash2==hasha2)
{
match[i-na+1]=1;
ct++;
}
}
printf("%d\n", ct);
ct=0;
for (i=0; i<nb && ct<1000; i++)
if (match[i])
{
printf("%d ", i);
ct++;
}
printf("\n");
return 0;
}