Pagini recente » Cod sursa (job #2601156) | Cod sursa (job #1870492) | Cod sursa (job #268116) | Cod sursa (job #2051160) | Cod sursa (job #2977612)
#include <fstream>
#include <cstring>
#define dim 2000001
#define mod1 999997
#define mod2 1000003
#define p 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[dim], b[dim];
int sol[dim];
int main()
{
int p1, p2, n, i, ha1, ha2, hb1, hb2, la, lb;
p1=p2=1;
ha1=ha2=hb1=hb2=0;
fin>>a>>b;
la=strlen(a);
lb=strlen(b);
if(la>lb)
{
fout<<0;
return 0;
}
for(i=0;i<la;i++)
{
ha1=(ha1*p+a[i])%mod1;
ha2=(ha2*p+a[i])%mod2;
hb1=(hb1*p+b[i])%mod1;
hb2=(hb2*p+b[i])%mod2;
if(i!=0)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
int nr=0;
if(ha1==hb1&&ha2==hb2)
{
nr++;
sol[nr]=0;
}
for(i=la;i<lb;i++)
{
hb1=((hb1-(b[i-la]*p1)%mod1+mod1)*p+b[i])%mod1;
hb2=((hb2-(b[i-la]*p2)%mod2+mod2)*p+b[i])%mod2;
if(ha1==hb1&&ha2==hb2)
{
nr++;
sol[nr]=i-la+1;
}
}
fout<<nr<<"\n";
nr=min(nr, 1000);
for(i=1;i<=nr;i++)
{
fout<<sol[i]<<" ";
}
return 0;
}