Pagini recente » Cod sursa (job #498606) | Cod sursa (job #2898364) | Cod sursa (job #1973305) | Cod sursa (job #2252706) | Cod sursa (job #2821999)
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
vector <int> v;
int base=97;
int mod=666019;
int base2=89;
int mod2=714199;
/*long long pow(int a,int putere,int Mod)
{
if(putere==1)
{
return a;
}
else if(putere%2==0)
{
long long p=pow(a,putere/2,Mod);
return p*p%Mod;
}
else
{
long long p=pow(a,putere/2,Mod);
return a*p*p%Mod;
}
}*/
long long Hash(int st, int dr, const string & x,int Base,int Mod)
{
long long rasp=0;
long long p=1;
for(int i=st;i<=dr;i++)
{
rasp=rasp+x[i]*p;
rasp=rasp%Mod;
p=p*Base;
p=p%Mod;
}
return rasp;
}
int main()
{
fin>>a;
fin>>b;
int lung_a=a.size();
int lung_b=b.size();
long long h_a=Hash(0,lung_a-1,a,97,666019);
long long h_a2=Hash(0,lung_a-1,a,89,714199);
long long h_b=Hash(lung_b-lung_a,lung_b-1,b,97,666019);
long long h_b2=Hash(lung_b-lung_a,lung_b-1,b,89,714199);
long long putere=1;
long long putere2=1;
for(int i=1;i<lung_a;i++)
{
putere=(putere*base)%mod;
putere2=(putere2*base2)%mod2;
}
int ult=lung_b-1;
if(h_b==h_a && h_b2==h_a2)
{
v.push_back(lung_b-lung_a);
}
for(int i=lung_b-lung_a;i>0;i--)
{
h_b=(h_b-(b[ult]*putere)%mod+mod)%mod;
h_b*=base;
h_b+=b[i-1];
h_b=h_b%mod;
h_b2=(h_b2-(b[ult]*putere2)%mod2+mod2)%mod2;
h_b2*=base2;
h_b2+=b[i-1];
h_b2=h_b2%mod2;
ult--;
if(h_b==h_a && h_b2==h_a2)
{
v.push_back(i-1);
}
}
int lung_v=v.size();
fout<<lung_v<<'\n';
int dist=min(1000,lung_v);
while(dist!=0)
{
dist--;
lung_v--;
fout<<v[lung_v]<<' ';
}
return 0;
}