Pagini recente » Cod sursa (job #1155947) | Cod sursa (job #1346334) | Cod sursa (job #663392) | Cod sursa (job #1039825) | Cod sursa (job #1529632)
#include <fstream>
#include <string.h>
#define M1 100003
#define M2 100847
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
char A[2000001],B[2000001];
int v[2000001];
int main()
{
in>>A>>B;
int la, lb, ha1, ha2, hb1, hb2, i, pmax1, pmax2, a, b, nr, poz, j;
pmax1=pmax2=1;
ha1=ha2=hb1=hb2=a=b=nr=poz=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[0]=0;
j=1;
}
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;
}