Cod sursa(job #3277766)

Utilizator catalinmarincatalinmarin catalinmarin Data 17 februarie 2025 13:20:57
Problema Potrivirea sirurilor Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int BASE_1 = 97;
const int BASE_2 = 101;
const int MOD_1 = 666013;
const int MOD_2 = 1000033;

long long MAX_EXPONENT_1 = 1;
long long MAX_EXPONENT_2 = 1;

string a, b;

long long hasher(const string &number, int BASE, int MOD){

    long long hashed_number = 0;
    long long exponent = 1;

    for (int i = a.size() - 1; i >= 0; i--){

        hashed_number += (number[i] - 'A') * exponent;
        exponent *= BASE;
        exponent %= MOD;
        hashed_number = hashed_number % MOD;
    }

    return hashed_number;
}

void solve(){

    fin >> a >> b;

    for (int i = 1; i < a.size(); i++){
        MAX_EXPONENT_1 *= BASE_1;
        MAX_EXPONENT_1 %= MOD_1;
        MAX_EXPONENT_2 *= BASE_2;
        MAX_EXPONENT_2 %= MOD_2;
    }

    long long hash_1_a = hasher(a, BASE_1, MOD_1);
    long long hash_2_a = hasher(a, BASE_2, MOD_2);

//    fout << hash_1_a << " " << hash_2_a << '\n';

    long long hash_1_b = hasher(b, BASE_1, MOD_1);
    long long hash_2_b = hasher(b, BASE_2, MOD_2);

//    fout << '\n';

//    fout << 0 << " " << hash_1_b << " " << hash_2_b << '\n';
    int to_delete = 0;
    vector<int> occurences;

    for (int i = a.size(); i < b.size(); i++){

        hash_1_b = (((((((hash_1_b - (MAX_EXPONENT_1 * (b[to_delete] - 'A'))) % MOD_1) + MOD_1) % MOD_1) * BASE_1)
                % MOD_1) + b[i] - 'A' % MOD_1) % MOD_1;

        hash_2_b = (((((((hash_2_b - (MAX_EXPONENT_2 * (b[to_delete] - 'A'))) % MOD_2) + MOD_2) % MOD_2) * BASE_2)
                    % MOD_2) + b[i] - 'A' % MOD_2) % MOD_2;

        to_delete++;

//        fout << to_delete << " " << hash_1_b << " " << hash_2_b << '\n';

        if (hash_1_a == hash_1_b && hash_2_a == hash_2_b) {
            occurences.push_back(to_delete);
        }
    }

    fout << occurences.size() << '\n';
    for (int p = 0; p < occurences.size() && p <= 999; p++){
        fout << occurences[p] << " ";
    }

}

int main(){

    solve();

    return 0;

}