Pagini recente » Cod sursa (job #3041325) | Cod sursa (job #174751) | Cod sursa (job #1013653) | Cod sursa (job #2597987) | Cod sursa (job #1529619)
#include <iostream>
#include <fstream>
#include <string.h>
#define M1 10007
#define M2 10103
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
char A[2000000],B[2000000];
int v[1001];
int n,m,la,lb;
int main()
{
in>>A>>B;
int ha1=0, ha2=0, hb1=0, hb2=0, i, pmax1=1, pmax2=1, a, b, nr=0, poz=0, j=0;
la=strlen(A);
lb=strlen(B);
if(la>lb)
out<<0;
else
{
for(i=0; i<la; i++)
{
ha1=(ha1*256+A[i])%M1;
ha2=(ha2*256+A[i])%M2;
hb1=(hb1*256+B[i])%M1;
hb2=(hb2*256+B[i])%M2;
pmax1=(pmax1*256)%M1;
pmax2=(pmax2*256)%M2;
}
if(ha1==hb1 && ha2==hb2)
{
nr++;
v[j]=0;
j++;
}
for(i=la; i<lb; i++)
{
a=(B[poz]*pmax1)%M1;
b=(B[poz]*pmax2)%M2;
poz++;
hb1=((hb1*256+B[i])%M1-a+M1)%M1;
hb2=((hb2*256+B[i])%M2-b+M2)%M2;
if(ha1==hb1 && ha2==hb2)
{
nr++;
v[j]=poz;
j++;
}
}
out<<nr<<'\n';
if(nr<=1000)
for(i=0;i<nr;i++)
out<<v[i]<<' ';
else
for(i=0;i<=1000;i++)
out<<v[i]<<' ';
}
in.close();
out.close();
return 0;
}