Pagini recente » Cod sursa (job #987912) | Cod sursa (job #670607) | Cod sursa (job #820576) | Cod sursa (job #1843858) | Cod sursa (job #2657720)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
typedef long long LL;
const LL baza=10007;
const LL m=10037;
LL rasp;
vector<LL> v;
int main()
{
string a, b;
fin>>a>>b;
if( a.size() > b.size() )
{
fout<<"Zero aparitii";
return 0;
}
LL n = a.size(), i;
LL vala = 0, valb = 0, put=1;
///fac hash-ul primului sir, cel pe care il caut
for(i = 0; i < n; i++)
{
vala = (vala * baza + a[i] ) % m;
put = (put * baza) % m;
}
//@cout<<"hash("<<a<<")="<<vala<<endl;
///Il fac pe al doilea
for(i = 0; i < n; i++)
valb = (valb * baza + b[i] ) % m;
//cout<<"Primul grup de litere are hashul: "<<valb<<endl;
if( vala == valb ) ++rasp;
///scad dimensiunea sirului cautat deoarece altfel as iesi cu o
///bucata din sirul mic in exteriorul/in dreapta sirului mare
for(i = 1; i <= b.size() - n; ++i){
valb = (valb * baza + b[i+n-1] ) % m;
///Fac smecheria de care va spuneam, adun nr prim m, ca sa nu am
///nr neg si sa ma gandesc la simetricul fata de adunare
LL ceva = (put * b[i-1]) % m;
valb = ( valb - ceva + m) % m;
///cout<<"valb="<<valb<<endl;
///cin.get();
///put = (put + baza) % B;
if( vala == valb ){
///cout<<" Potrivire pe poz: "<< i << endl;
///cout<<"v.size()="<<v.size()<<"\n";
++rasp;
///if( v.size() < 1000 )
v.push_back( i );
}
}
///Nr potriviri =
fout << rasp << "\n";
for( i = 0; i < v.size(); ++i )
fout<<v[i]<<" ";
return 0;
}