Pagini recente » Cod sursa (job #619001) | Cod sursa (job #3226647) | Cod sursa (job #2150120) | Cod sursa (job #586118) | Cod sursa (job #2664410)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> RabinKarp(string ce_caut, string text)
{
const int p = 100;
const int m = 1000000007;
int n1 = ce_caut.size(), n2 = text.size(), i;
const int dim_max = max(n1, n2);
vector<long long> put(dim_max);
put[0] = 1;
for (i = 1; i < (int)put.size(); ++i)
put[i] = (put[i - 1] * p) % m;
/// hashul textului
vector<long long> h(n2 + 1, 0);
for (i = 1; i <= n2; ++i)
h[i] = (h[i - 1] + (text[i - 1]) * put[i - 1]) % m;
/// hash-ul sirului cautat
long long h_cautat = 0;
for (i = 0; i < n1; ++i)
h_cautat = (h_cautat + (ce_caut[i]) * put[i]) % m;
vector<int> aparitii;
long long hash_actual;
for (i = 0; i <= n2 - n1; ++i)
{
hash_actual = (h[i + n1] - h[i] + m) % m;
/// dc e nevoie, pot opri functia dupa prima gasire
if (hash_actual == (h_cautat * put[i]) % m && aparitii.size() < 1000)
aparitii.push_back(i);
}
return aparitii;
}
void afiseaza_pozitiile(vector<int> v)
{
cout << v.size() << '\n';
for (int i = 0; i < v.size() ; ++i)
cout << v[i] << " ";
cout << '\n';
}
int main()
{
string mic, mare;
cin >> mic;
cin >> mare;
vector<int> v = RabinKarp(mic, mare);
afiseaza_pozitiile(v);
return 0;
}