Cod sursa(job #2453911)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 6 septembrie 2019 15:14:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <unordered_map>

using namespace std;

class rolling_hash{

private:

    int base;
    int mod;
    int len;
    int h;

    int pwr;

public:

    rolling_hash(int base, int mod, int len): base{base}, mod{mod}, len{len}{
        pwr = 1;

        for (int i = 1; i <= len - 1; i++){
            pwr = (pwr * base) % mod;
        }

        h = 0;
    }

    void add(char c){
        h = (h * base + c) % mod;
    }

    void remove(char c){
        h = (h - (pwr * c) % mod + mod) % mod;
    }

    int get_hash(){
        return h;
    }
};

int main() {
    ios_base::sync_with_stdio(false);

    ifstream in("data.txt");
    ofstream out("strmatch.out");

    string a, b;
    in >> a >> b;

    if (a.size() > b.size()){
        cout << "0\n";
        return 0;
    }

    rolling_hash h1_a(91, 666013, a.size());
    rolling_hash h2_a(97, 666013, a.size());

    for (char c: a){
        h1_a.add(c);
        h2_a.add(c);
    }

    rolling_hash h1_b(91, 666013, a.size());
    rolling_hash h2_b(97, 666013, a.size());

    for (size_t i = 0; i < a.size() - 1; i++){
        h1_b.add(b[i]);
        h2_b.add(b[i]);
    }

    vector<int> matches;

    for (size_t i = a.size() - 1; i < b.size(); i++){
        h1_b.add(b[i]);
        h2_b.add(b[i]);

        if (h1_a.get_hash() == h1_b.get_hash()){
            matches.push_back(i);
        }

        h1_b.remove(b[i - a.size() + 1]);
        h2_b.remove(b[i - a.size() + 1]);
    }

    out << matches.size() << endl;

    for (int x: matches){
        out << x - a.size() + 1 <<  " " ;
    }

    out << endl;

    return 0;
}