Pagini recente » Cod sursa (job #1313937) | Cod sursa (job #952159) | Cod sursa (job #1736120) | Cod sursa (job #1038080) | Cod sursa (job #1838275)
#include <bits/stdc++.h>
#define baza 73
#define mod1 100007
#define mod2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b,s;
vector <int> t;
int n,m,i,nr;
int hasha1,hasha2,hashb1,hashb2,hb1,hb2;
int main()
{
fin>>a>>b;
n=a.length();
m=b.length();
hb1=1;
hb2=1;
for (i=0; i<n; i++)
{
//Hashuim subsirul
hasha1=(hasha1*baza+a[i]) % mod1;
hasha2=(hasha2*baza+a[i]) % mod2;
//Hashuim primele n caractere din sirul nostru
hashb1=(hashb1*baza+b[i]) % mod1;
hashb2=(hashb2*baza+b[i]) % mod2;
if (i==0) continue;
//Cream hashurile adaugatoare pentru sirul nostru
hb1=(hb1*baza) % mod1;
hb2=(hb2*baza) % mod2;
}
//Verificam daca hashurile coincid
for (i=0; i<=m-n; i++)
{
if (hasha1==hashb1 && hasha2==hashb2) { nr++; if (nr<=999) t.push_back(i); }
//Eliminam primul caracter din hash-ul sirului nostru si adaugam urmatorul :
hashb1=((hashb1 - (b[i]*hb1) % mod1 + mod1) * baza + b[i+n]) % mod1;
hashb2=((hashb2 - (b[i]*hb2) % mod2 + mod2) * baza + b[i+n]) % mod2;
}
fout<<nr<<'\n';
for (i=0; i<1000; i++)
fout<<t[i]<<" ";
return 0;
}