Pagini recente » Cod sursa (job #1190495) | Cod sursa (job #1652843) | Cod sursa (job #1650885) | Borderou de evaluare (job #1036644) | Cod sursa (job #1527944)
#include <fstream>
#include <string.h>
#define M1 100129
#define M2 100907
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000005],b[2000005];
int main()
{
int i,x,y,hashb1=0,hashb2=0,hasha1=0,hasha2=0,q=0,aux1=0;
int nr=0,inceputuri[1001],p=0,putmax1=1,putmax2=1,aux2=0;
in>>b>>a;
x=strlen(a);
y=strlen(b);
for(i=0;i<y;i++)
{
hashb1=(hashb1*256+b[i])%M1;
hashb2=(hashb2*256+b[i])%M2;
hasha1=(hasha1*256+a[i])%M1;
hasha2=(hasha2*256+a[i])%M2;
putmax1=(putmax1*256)%M1;
putmax2=(putmax2*256)%M2;
}
if((hasha1==hashb1) && (hasha2==hashb2))
{
nr++;
inceputuri[p]=0;
p++;
}
//out<<"hasha1= "<<hasha1<<"\t hasha2= "<<hasha2<<"\t hashb1= "<<hashb1<<"\t hashb2= "<<hashb2<<"\n";
for(i=y;i<x;i++)
{
aux1=(a[q]*putmax1)%M1;
aux2=(a[q]*putmax2)%M2;
q++;
hasha1=((hasha1*256+a[i])%M1-aux1+M1)%M1;
hasha2=((hasha2*256+a[i])%M2-aux2+M2)%M2;
//out<<"hasha1= "<<hasha1<<"\t hasha2= "<<hasha2<<"\n";
if((hasha1==hashb1) && (hasha2==hashb2))
{
nr++;
inceputuri[p]=q;
p++;
}
}
out<<nr<<"\n";
if(nr==0){
if(nr<=1000)
{
for(i=0;i<nr;i++) out<<inceputuri[i]<<" ";
}else for(i=0;i<1000;i++) out<<inceputuri[i]<<" ";
}
in.close();
out.close();
return 0;
}