Cod sursa(job #3310754)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 16 septembrie 2025 16:58:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

using u64 = unsigned long long; ///folosim unsigned long long

const int BASE = 67;

int get_c(char c) {
    if(c >= '0' && c <= '9') {
        return c - '0' + 1;
    }
    else if(c >= 'a' && c <= 'z') {
        return c - 'a' + 11;
    }
    else {
        return c - 'A' + 37;
    }
}

u64 comp_hash(string X) {
    u64 ret = 0;
    for(int i = 0; i < X.size(); i++) {
        ret = ret * BASE + get_c(X[i]);
    }
    return ret;
}

int main()
{
    string A, B;
    fin >> A >> B;
    
    u64 ha = comp_hash(A);
    
    
    u64 BASE_TO_N = 1;
    for(int i = 1; i <= A.size(); i++) {
        BASE_TO_N *= BASE;
    }
    
    vector<int> sol;
    sol.reserve(B.size());
    u64 rolling_hash = 0;
    for(int i = 0; i < B.size(); i++) {
        rolling_hash = rolling_hash * BASE + get_c(B[i]);
        if(i >= A.size()) {
            rolling_hash -= BASE_TO_N * get_c(B[i - A.size()]);
        }
        if(i >= A.size() - 1) {
            if(rolling_hash == ha) {
                sol.push_back(i);
            }
        }
    }
    if(sol.size() > 1000) {
        sol.resize(1000);
    }
    fout << sol.size() << "\n";
    for(auto s : sol) {
        fout << s - A.size() + 1 << " ";
    }
    fout << "\n";
    return 0;
}