Pagini recente » Cod sursa (job #704294) | Cod sursa (job #1729726) | Cod sursa (job #1636995) | Cod sursa (job #2279594) | Cod sursa (job #2822046)
#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 Hash(int st, int dr, const string & x,int Base,int Mod)
{
long long rasp=0;
long long p=1;
for(int i=dr;i>=st;i--)
{
rasp=rasp+x[i]*p;
rasp=rasp%Mod;
p=p*Base;
p=p%Mod;
}
return rasp;
}
void avanseaza_hash(int & hash_b, int putere, int Mod, int Base, char urm, char primul)
{
hash_b=(hash_b-(1LL*primul*putere)%Mod+Mod)%Mod;
hash_b=(hash_b*Base)%Mod;
hash_b+=urm;
hash_b=hash_b%Mod;
}
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);
int h_b=Hash(0,lung_a-1,b,97,666019);
int h_b2=Hash(0,lung_a-1,b,89,714199);
int putere=1;
int putere2=1;
for(int i=1;i<lung_a;i++)
{
putere=(1LL*putere*base)%mod;
putere2=(1LL*putere2*base2)%mod2;
}
int primul=0;
int nr_elem=0;
h_a2=0;
h_b2=0;
if(h_a==h_b && h_a2==h_b2)
{
v.push_back(0);
nr_elem++;
}
for(int i=lung_a;i<lung_b;i++)
{
avanseaza_hash(h_b,putere,mod,base,b[i],b[primul]);
//avanseaza_hash(h_b2,putere2,mod2,base2,b[i],b[primul]);
primul++;
if(h_a==h_b && h_a2==h_b2 && v.size()<1000)
{
v.push_back(primul);
}
if(h_a==h_b && h_a2==h_b2)
{
nr_elem++;
}
}
fout<<nr_elem<<'\n';
for(int i=0;i<v.size();i++)
{
fout<<v[i]<<' ';
}
return 0;
}