Pagini recente » Cod sursa (job #279101) | Cod sursa (job #1000205) | Cod sursa (job #2916185) | Cod sursa (job #705490) | Cod sursa (job #2871563)
#include <fstream>
#include <vector>
#include <string>
#define mod1 1000000007
#define mod2 1000000013
#define prim1 31
#define prim2 37
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
unsigned long long p1=1,p2=1,hasha1,hasha2,hashb1,hashb2;
int sa,sb,nr,i;
vector<int>rez;
int main()
{
f>>A>>B;
sa=A.size();
sb=B.size();
if(sa>sb)
{
g<<"0";
return 0;
}
//hash primul sir
for(i=0;i<sa;i++)
{
hasha1=((hasha1*prim1)%mod1+A[i])%mod1;
hasha2=((hasha2*prim2)%mod2+A[i])%mod2;
if(i!=0)
{
p1=(p1*prim1)%mod1;
p2=(p2*prim2)%mod2;
}
}
//hash primele caractere din al doilea sir
for(i=0;i<sa;i++)
{
hashb1=((hashb1*prim1)%mod1+B[i])%mod1;
hashb2=((hashb2*prim2)%mod2+B[i])%mod2;
}
if(hasha1==hashb1&&hasha2==hashb2)
{
nr++;
rez.push_back(0);
}
//hash restul sirului
for(i=sa;i<sb;i++)
{
hashb1=((prim1*(hashb1-((B[i-sa]*p1)%mod1)+mod1))%mod1+B[i])%mod1;
hashb2=((prim2*(hashb2-((B[i-sa]*p2)%mod2)+mod2))%mod2+B[i])%mod2;
if(hashb1==hasha1&&hashb2==hasha2)
{
rez.push_back(i-sa+1);
nr++;
}
}
g<<nr<<'\n';
for(i=0;i<nr&&i<1000;i++) g<<rez[i]<<" ";
return 0;
}