Cod sursa(job #3329598)

Utilizator llaris_a23Larisa Alexandra Videnie llaris_a23 Data 14 decembrie 2025 13:58:04
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <vector>
#define baza 62
#define mod1 100007
#define mod2 100021

using namespace std;

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

string A, B;
long long hash1, hash2;

int bazaC(char c) {
    if (c >= 'A' && c <= 'Z') {
        c = 1 + c - 'A';
    }
    else if (c >= 'a' && c <= 'z') {
        c = 27 + c - 'a';
    }
    else {
        c = 53 + c - '0';
    }

    return c;
}

int main() {

    fin >> A >> B;

    int nr1 = 0, nr2 = 0, p1 = 1, p2 = 1;

    for (int i = 0; i < A.size(); i++) {
        int cod = bazaC(A[i]);
        nr1 = (nr1 * baza + cod) % mod1;
        nr2 = (nr2 * baza + cod) % mod2;
        p1 = (p1 * baza) % mod1;
        p2 = (p2 * baza) % mod2;
    }

    hash1 = nr1;
    hash2 = nr2;

    int cnt = 0;
    vector<int> v;

    if (B.size() < A.size()) {
        fout << 0;
        return 0;
    }
    else {
        nr1 = 0, nr2 = 0;
        for (int i = 0; i < A.size(); i++) {
            int cod = bazaC(B[i]);
            nr1 = (nr1 * baza + cod) % mod1;
            nr2 = (nr2 * baza + cod) % mod2;
        }

        if (nr1 == hash1 && nr2 == hash2) {
            cnt++;
            v.push_back(1);
        }

        for (int i = A.size(); i < B.size(); i++) {
            int cod = bazaC(B[i]);
            nr1 = (nr1 * baza + cod) % mod1;
            nr2 = (nr2 * baza + cod) % mod2;

            int cod2 = bazaC(B[i - A.size()]);
            nr1 = ((nr1 - cod2 * p1) % mod1 + mod1) % mod1;
            nr2 = ((nr2 - cod2 * p2) % mod2 + mod2) % mod2;

            if (nr1 == hash1 && nr2 == hash2) {
                cnt++;
                v.push_back(i - A.size() + 1);
            }
        }

        fout << cnt << '\n';

        for (int i = 0; i < v.size(); i++) {
            fout << v[i] << ' ';
        }
    }

}