Pagini recente » Cod sursa (job #271801) | Cod sursa (job #1901633) | Cod sursa (job #1068860) | Cod sursa (job #860771) | Cod sursa (job #2657515)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream gout("strmatch.out");
typedef long long LL;
const LL baza =10007 ;
const LL m = 10037;
/// Facem, mai intai, cu un singur hash.
LL rasp; /// Nr de potriviri
/// mai trebuie sa mai retin si pozitiile
vector<LL>v;
int main()
{
string a, b;
fin >> a >> b;
if( a .size() > b.size() )
{
gout <<0;
return 0;
}
LL n = a.size(), i;
LL vala = 0, valb = 0, put = 1;
/// fac hash-ul primullui 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 n litere are hashul:" << valb << endl;
if( vala == valb )
{
++rasp;
v.push_back(0);
}
/// 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 negative
/// si sa ma gandesc la simetricul fata de adunare
///cout<<"valb = " << valb<<" ";
LL ceva = (put * b[i-1]) % m; /// l-am facut pozitiv
valb = ( (valb - ceva)%m +m) % m;///ma gandesc daca scriu dir sau o alta var.
///cout << "ceva = " << ceva << endl;
///cout << "valb = " << valb << endl;
if( vala == valb )
{
++rasp;
///cout << "Potrivire pe poz " << i << endl;
if(v.size() < 1000)
v.push_back(i);
}
}
gout <<rasp << endl;
for(int j = 0; j < v.size(); j++)
{
gout<<v[j]<<" ";
}
return 0;
}