Pagini recente » Cod sursa (job #687906) | Cod sursa (job #2220027) | Cod sursa (job #270646) | Cod sursa (job #2395379) | Cod sursa (job #1320671)
#include <iostream>
#include <fstream>
#include <cstring>
#define mod1 100007
#define mod2 100021
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000010],b[2000010];
int la,lb,sol[2000010],nr;
int main()
{
f>>a; f>>b;
la=strlen(a); lb=strlen(b); //lungimile sirurilor
int i,baza=26,coda=0,codb=0,coda1=0,codb1=0;
int pa=1,pa1=1; //puterea maxima a lui 26 in scrierea lui a
for(i=0;i<la;i++)
{
coda=(coda*baza+a[i])%mod1;
coda1=(coda1*baza+a[i])%mod2;
if(i>0)
{pa=pa*baza; pa1=pa1*baza;}
}
for(i=0;i<la;i++)
{
codb=(codb*baza+b[i])%mod1;
codb1=(codb1*baza+b[i])%mod2;
}
if(coda==codb && coda1==codb1)
{
sol[0]=1;
nr++;
}
for(i=la;i<lb;i++)
{
codb=((codb-(b[i-la]*pa)%mod1 + mod1)*baza+b[i])%mod1;
codb1=((codb1-(b[i-la]*pa)%mod2 + mod2)*baza+b[i])%mod2;
if(coda==codb && coda1==codb1)
{
sol[i-la+1]=1;
nr++;
}
}
g<<nr<<endl;
nr=0;
for(i=0;i<lb && nr<1000;i++)
if(sol[i]==1)
{g<<i<<" ";nr++;}
g<<endl;
f.close(); g.close();
return 0;
}