Pagini recente » Cod sursa (job #2206159) | Cod sursa (job #3001578) | Cod sursa (job #1802185) | Cod sursa (job #675296) | Cod sursa (job #2657085)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("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
vector<LL> v;/// mai trebuie sa mai retin si pozitiile
int main()
{
string a, b;
f >> a >> b;
if( a .size() > b.size() )
{
g<<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;
}
/// Il fac pe al doilea
for( i = 0; i < n; ++i )
valb = ( valb * baza + b[i] ) % m;
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
LL ceva = (put * b[i-1]) % m + m; /// l-am facut pozitiv
valb = ((valb - ceva ) % m + m) % m; ///ma gandesc daca scriu dir sau o alta var.
///put = (put * baza) % B;
if( vala == valb)
{
++rasp;
if(v.size() < 1000)
v.push_back(i);
}
}
g<<rasp<<endl;
for(int j = 0; j < v.size(); j++){
g<<v[j]<<" ";
}
return 0;
}