Pagini recente » Cod sursa (job #2314805) | Cod sursa (job #1512813) | Cod sursa (job #839761) | Cod sursa (job #1292402) | Cod sursa (job #2702388)
#include <fstream>
#include <vector>
using namespace std;
const unsigned long long int base=1010012383;
const unsigned long long int mod=1010012359;
long long int hasha,hashb; // astea sunt hash-urile
long long int plm,pow;
int i;
int c=0; // numarul de secvente gasite
string a,b;
vector<int>v;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main()
{
cin>>a>>b;
pow=1;
if (a.size()>b.size()) // daca sirul a este mai lung ca b
{
cout<<0;
return 0;
}
for (i=0;i<a.size();i++) // se face hasu-ul lui a
{
hasha=(hasha*base+a[i])%mod;
pow=(pow*base)%mod;
}
for (i=0;i<a.size();i++) // se face prima partehash-ul lui b
{
hashb=(hashb*base+b[i])%mod;
}
if (hasha==hashb)
{
if (v.size()<1000) v.push_back(0);
c++;
}
for (i=1;i<b.size()-a.size();i++) // scad dimensiunea sirului cautat pentru a nu ajunge in exteriorul sirului cautat, in dreapta
{
hashb=(hashb*base+b[i+a.size()-1])%mod;
plm=(pow*b[i-1])%mod;
hashb=(hashb-plm+mod)%mod;
if (hasha==hashb)
{
if (v.size()<1000) v.push_back(i);
c++;
}
}
cout<<c<<"\n";
for (i=0;i<v.size();i++) cout<<v[i]<<" ";
}