Pagini recente » Cod sursa (job #775927) | Cod sursa (job #2342251) | tema | Cod sursa (job #2126877) | Cod sursa (job #2657501)
#include <iostream>
#include <fstream>
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,v[m],j,ceva; /// Nr de potriviri
/// mai trebuie sa mai retin si pozitiile
int main()
{
string a, b;
fin >> a >> b;
if( a .size() > b.size() )
{
cout << "Zero aparitii";
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 );
}
///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[j++]=1;
}
/// 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<<" ";
ceva = (put * b[i-1]) % m ; /// l-am facut pozitiv
valb = ( valb - ceva +m) % m;///ma gandesc daca scriu dir sau o alta var.
///cout << "ceva = " << ceva << endl;
///cout << "valb = " << valb << endl;
if( vala == valb )
{
///cout << "Potrivire pe poz " << i << endl;
v[j++]=i;
++rasp;
}
}
gout <<rasp << endl;
j=0;
while(v[j])
{
gout<<v[j++]<<" ";
}
return 0;
}