Pagini recente » Cod sursa (job #1527136) | Cod sursa (job #1809667) | Cod sursa (job #3166957) | Cod sursa (job #1862832) | Cod sursa (job #1315648)
#include <iostream>
#include<fstream>
#include<cstring>
#define mod1 100007
#define mod2 100021
using namespace std;
char a[2000010],b[2000010];
int lga,lgb;
int sol[2000010];
void citire()
{
ifstream fin("strmatch.in");
fin>>a;
fin>>b;
fin.close();
lga=strlen(a);
lgb=strlen(b);
}
void solve()
{
ofstream fout("strmatch.out");
int base=73,base1,base2,code1,code2,i;
base1=base2=1;
code1=code2=0;
for(i=0;i<lga;++i)
{
code1=(code1*base + a[i])%mod1;
code2=(code2*base + a[i])%mod2;
if(i!=0)
{
base1=(base1*base)%mod1;
base2=(base2*base)%mod2;
}
}
if(lga > lgb)
{
fout<<"0\n";
}
else
{
int codeb1=0,codeb2=0;
for(i=0;i<lga;++i)
{
codeb1=(codeb1*base + b[i]) % mod1;
codeb2=(codeb2*base + b[i]) % mod2;
}
int nr=0;
if(code1==codeb1 && code2==codeb2)
{
cout<<"muie";
sol[0]=1;
++nr;
}
for(i=lga;i<lgb;++i)
{
codeb1=((codeb1-(b[i-lga]*base1)%mod1 + mod1)*base + b[i])%mod1;
codeb2=((codeb2-(b[i-lga]*base2)%mod2 + mod2)*base+ b[i]) % mod2;
if(code1==codeb1 && code2==codeb2)
{
sol[i- lga + 1]=1;
++nr;
}
}
fout<<nr<<"\n";
nr=0;
for(i=0;i<lgb && nr<1000 ; ++i)
if(sol[i]==1)
{
nr++;
fout<<i<<" ";
}
}
fout.close();
}
int main()
{
citire();
solve();
return 0;
}