Pagini recente » Cod sursa (job #2211662) | Cod sursa (job #3186322) | Cod sursa (job #2366553) | Cod sursa (job #1507822) | Cod sursa (job #2871554)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long mod1=1e9+7,mod2=1e9+13,prim1=31,prim2=37;
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=((hashb1-((B[i-sa]*p1)%mod1)+mod1)*prim1%mod1+B[i])%mod1;
hashb2=((hashb2-((B[i-sa]*p2)%mod2)+mod2)*prim2%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++) g<<rez[i]<<" ";
return 0;
}