Cod sursa(job #2664410)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 28 octombrie 2020 16:39:14
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#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;
}