Pagini recente » Cod sursa (job #2242598) | Cod sursa (job #1030317) | Cod sursa (job #1926247) | Cod sursa (job #3225519) | Cod sursa (job #543959)
Cod sursa(job #543959)
#include<stdio.h>
#include<string.h>
const int maxp=2000001;
const int p=73;
const int m1=100007;
const int m2=100021;
char a[maxp],b[maxp],m[maxp];
int i,nr1,nr2,h1,h2,d1=1,d2=1,ha1,ha2,sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
nr1=strlen(a);
nr2=strlen(b);
if(nr1>nr2)
{
printf("0");
return 0;
}
for(i=0;i<nr1;i++)
{
ha1=(ha1*p+a[i])%m1;
ha2=(ha2*p+a[i])%m2;
h1=(h1*p+b[i])%m1;
h2=(h2*p+b[i])%m2;
}
for(i=1;i<nr1;i++)
{
d1=(d1*p)%m1;
d2=(d2*p)%m2;
}
if(h1==ha1&&h2==ha2)
sol++, m[0]=1;
for(i=nr1;i<nr2;i++)
{
h1=((h1-(b[i-nr1]*d1)%m1+m1)*p+b[i])%m1;
h2=((h2-(b[i-nr1]*d2)%m2+m2)*p+b[i])%m2;
if(h1==ha1&&h2==ha2)
sol++, m[i-nr1+1]=1;
}
printf("%d\n",sol);
sol=0;
for(i=0;i<nr2&&sol<1000;i++)
if(m[i]==1)
printf("%d ",i),sol++;
return 0;
}