Pagini recente » Borderou de evaluare (job #1196502) | Cod sursa (job #1030903) | Cod sursa (job #511574) | Cod sursa (job #688861) | Cod sursa (job #2656336)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long A = 1606081;
const long long B = 71111113;
vector<int>sol;
int main()
{
long long rasp = 0, put, x;
string a, b;
cin >> a >> b;
if (a.size() > b.size())
{
cout << 0;
return 0;
}
long long n = a.size(), i, j, m = b.size();
long long valb = 0, vala = 0; /// valorile hashului
put = 1;
for (i = 0; i < n; ++i)
{
vala = (vala * A + a[i]) % B;
put = (put * A) % B;
}
for (i = 0; i < n; ++i)
valb = (valb * A + b[i]) % B;
if (vala == valb)
++rasp, sol.push_back(1);
for (i = 1; i <= m - n; ++i)
{
valb = (valb * A + b[i + n - 1]) % B;
x = put * b[i - 1];
valb = (((valb - x) % B) + B) % B;
if (vala == valb)
{
++rasp;
sol.push_back(i);
}
}
cout << rasp << endl;
for (int i = 0; i < min((int)sol.size(), 1000); i++)
cout << sol[i] << " ";
cout << "\n";
return 0;
}