Pagini recente » Cod sursa (job #1934276) | Cod sursa (job #792063) | Cod sursa (job #1725750) | Cod sursa (job #2559264) | Cod sursa (job #2656339)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long A = 1606081;
const long long B = 71111113;
vector<int>sol;
int main()
{
long long rasp = 0, put, x;
string a, b;
fin >> a >> b;
if (a.size() > b.size())
{
fout << 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);
}
}
fout << rasp << endl;
for (int i = 0; i < min((int)sol.size(), 1000); i++)
fout << sol[i] << " ";
fout << "\n";
return 0;
}