Pagini recente » Cod sursa (job #1960783) | Cod sursa (job #464923) | Borderou de evaluare (job #2016039) | Cod sursa (job #701089) | Cod sursa (job #2871564)
#include<bits/stdc++.h>
#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;
}