Pagini recente » Cod sursa (job #1603799) | Cod sursa (job #89500) | Cod sursa (job #196572) | Cod sursa (job #2825161) | Cod sursa (job #1855583)
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int na,nb,i,ha1,ha2,hb1,hb2,p1,p2,bz,nr,d1,d2,c;
char a[2000002],b[2000002],x[2000002];
int main()
{
f>>a;
na=strlen(a);
bz=73;
p1=100007;
p2=100021;
ha1=0;
ha2=0;
nr=0;
for(i=0;i<=na-1;i++)
{
ha1=(ha1*bz+a[i])%p1;
ha2=(ha2*bz+a[i])%p2;
}
f>>b;
nb=strlen(b);
hb1=0; hb2=0;
for(i=0;i<=na-1;i++)
{
hb1=(hb1*bz+b[i])%p1;
hb2=(hb2*bz+b[i])%p2;
}
if(hb1==ha1&&hb2==ha2)
{
nr++;
x[0]=1;
}
d1=1; d2=1;
for(i=1;i<=na-1;i++)
{
d1=(d1*bz)%p1;
d2=(d2*bz)%p2;
}
for(i=na;i<=nb-1;i++)
{
hb1=((hb1-(d1*b[i-na])%p1+p1)*bz+b[i])%p1;
hb2=((hb2-(d2*b[i-na])%p2+p2)*bz+b[i])%p2;
if(hb1==ha1&&hb2==ha2)
{
nr++;
x[i-na+1]=1;
}
}
g<<nr<<'\n';
c=0;
for(i=0;i<=nb-na;i++)
{
if(x[i]==1)
{c++;
if(c<1001) g<<i<<" ";
}
}
f.close();
g.close();
return 0;
}