Pagini recente » Cod sursa (job #31202) | Cod sursa (job #148023) | Cod sursa (job #991964) | Cod sursa (job #3203182) | Cod sursa (job #2978934)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
const int mod1=999997;
const int mod2=1000003;
int ha1,ha2,nr,hb1,hb2;
vector<int>sol;
int main()
{
f>>a>>b;
int p1,p2,p;
p1=p2=1;
p=73;
if(a.size()>b.size())
{
g<<0;
return 0;
}
for(int i=0;i<a.size();i++)
{
ha1=(ha1*p+(a[i]-'A'+1))%mod1;
ha2=(ha2*p+(a[i]-'A'+1))%mod2;
hb1=(hb1*p+(b[i]-'A'+1))%mod1;
hb2=(hb2*p+(b[i]-'A'+1))%mod2;
if(i)
{
p1=(p*p1)%mod1;
p2=(p*p2)%mod2;
}
}
if(ha1==hb1&&ha2==hb2)
sol.push_back(0),nr++;
for(int i=a.size();i<b.size();i++)
{
int last=(b[i-a.size()]-'A'+1);
int next=b[i]-'A'+1;
hb1=((hb1-(last*p1)%mod1+mod1)*p+next)%mod1;
hb2=((hb2-(last*p2)%mod2+mod2)*p+next)%mod2;
if(ha1==hb1&&ha2==hb2)
sol.push_back(i-a.size()+1),nr++;
}
g<<nr<<'\n';
for(auto x : sol)
g<<x<<" ";
return 0;
}