Cod sursa(job #3333272)

Utilizator abetAlbert Voiculescu abet Data 12 ianuarie 2026 17:39:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);
    string A, B;
    in >> A >> B;
    int m = A.size();
    int n = B.size();
    if (m > n) {
        out << 0 << "\n";
        return 0;
    }
    const uint64_t BASE1 = 1315423911ULL;
    const uint64_t BASE2 = 11400714819323198485ULL;
    uint64_t hashA1 = 0, hashB1 = 0;
    uint64_t hashA2 = 0, hashB2 = 0;
    uint64_t power1 = 1, power2 = 1;
    for (int i = 0; i < m; i++) {
        hashA1 = hashA1 * BASE1 + (unsigned char)A[i];
        hashB1 = hashB1 * BASE1 + (unsigned char)B[i];
        hashA2 = hashA2 * BASE2 + (unsigned char)A[i];
        hashB2 = hashB2 * BASE2 + (unsigned char)B[i];
        if (i < m - 1) {
            power1 *= BASE1;
            power2 *= BASE2;
        }
    }
    vector<int> pos;
    long long total = 0;
    for (int i = 0; i <= n - m; i++) {
        if (hashA1 == hashB1 && hashA2 == hashB2) {
            total++;
            if ((int)pos.size() < 1000)
                pos.push_back(i);
        }
        if (i + m < n) {
            hashB1 -= power1 * (unsigned char)B[i];
            hashB1 = hashB1 * BASE1 + (unsigned char)B[i + m];
            hashB2 -= power2 * (unsigned char)B[i];
            hashB2 = hashB2 * BASE2 + (unsigned char)B[i + m];
        }
    }
    out << total << "\n";
    for (int x : pos)
        out << x << " ";
    out << "\n";

    return 0;
}