Pagini recente » Cod sursa (job #2902094) | Cod sursa (job #233318) | Cod sursa (job #442909) | Cod sursa (job #2051985) | Cod sursa (job #1023617)
#include<stdio.h>
#include<string.h>
using namespace std;
#define MOD1 100007
#define MOD2 100021
#define B 73
char a[2000003],b[2000002],n,m;
int ha1,ha2,hb1,hb2;
int poz[2000003];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i,sol=0,b1=1,b2=1;
scanf("%s\n%s",&a,&b);
n=strlen(a);
m=strlen(b);
if(n>m)
{
printf("0\n");
return 0;
}
///////////////
for(i=0;i<n;++i)
{
ha1=(ha1*B+a[i])%MOD1;
ha2=(ha2*B+a[i])%MOD2;
}
for(i=0;i<n;++i)
{
hb1=(hb1*B+b[i])%MOD1;
hb2=(hb2*B+b[i])%MOD2;
}
if(ha1==hb1 &&ha2==hb2)
poz[++sol]=0;
for(i=1;i<n;++i)
{
b1=(b1*B)%MOD1;
b2=(b2*B)%MOD2;
}
for(;i<m;++i)
{
hb1=(((hb1-b[i-n]*b1)%MOD1+MOD1)*B+b[i]) %MOD1;
hb2=(((hb2-b[i-n]*b2)%MOD2+MOD2)*B+b[i]) %MOD2;
if(ha1==hb1 &&ha2==hb2)
poz[++sol]=i-n+1;
}
printf("%d\n",sol);
if(sol>1000)
sol=1000;
for(i=1;i<=sol;++i)
printf("%d ",poz[i]);
printf("\n");
return 0;
}