Pagini recente » Cod sursa (job #2640031) | Cod sursa (job #284320) | Cod sursa (job #2008560) | Cod sursa (job #1571694) | Cod sursa (job #1023626)
#include<stdio.h>
#include<string.h>
using namespace std;
#define MOD1 100007
#define MOD2 100013
#define B 87
char a[2000003],b[2000002];
int ha1,ha2,hb1,hb2,n,m;
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;
}