Pagini recente » Cod sursa (job #390233) | Cod sursa (job #1105751) | Cod sursa (job #1891869) | Cod sursa (job #2937465) | Cod sursa (job #1827980)
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000002],b[2000002];
int B,p1,p2,na,nb,ha1,ha2,x[1002],c,i,r1,r2,hb1,hb2,d;
int main()
{
fin>>a>>b;
B=97;
p1=99991;
p2=88427;
na=strlen(a);
nb=strlen(b);
ha1=0;
ha2=0;
for(i=0;i<=na-1;i++)
{
ha1=(ha1*B+a[i])%p1;
ha2=(ha2*B+a[i])%p2;
}
r1=1;
r2=1;
for(i=1;i<=na-1;i++)
{
r1=(r1*B)%p1;
r2=(r2*B)%p2;
}
hb1=0;
hb2=0;
for(i=0;i<=na-1;i++)
{
hb1=(hb1*B+b[i])%p1;
hb2=(hb2*B+b[i])%p2;
}
c=0;
if(ha1==hb1&&ha2==hb2)
{
c++;
x[c]=0;
}
for(i=na;i<=nb-1;i++)
{
hb1=(hb1-(b[i-na]*r1)%p1+p1)%p1;
hb1=(hb1*B+b[i])%p1;
hb2=(hb2-(b[i-na]*r2)%p2+p2)%p2;
hb2=(hb2*B+b[i])%p2;
if(ha1==hb1&&ha2==hb2)
{
c++;
if(c<=1000)
{
x[c]=i-na+1;
}
}
}
fout<<c<<endl;
d=c;
if(d>1000)
{
d=1000;
}
for(i=1;i<=d;i++)
{
fout<<x[i]<<" ";
}
fin.close();
fout.close();
return 0;
}