Cod sursa(job #3315029)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 11 octombrie 2025 22:09:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 100;
const int BASE = 26;
const char HASHER = '0';

char A[NMAX], B[NMAX];

int HashEntireString(const char s[]) {
    int hash = 0;
    for (int i = 0; s[i]; i++) {
        hash = hash * BASE + (s[i] - HASHER);
    }
    return hash;
}

int main() {
    cin >> A >> B;
    int n = strlen(A);
    int m = strlen(B);

    if (n > m) {
        cout << 0;
        return 0;
    }

    int hash_A = HashEntireString(A);
    int current_hash = 0;
    int power = 1;


    for (int i = 0; i < n - 1; i++) power *= BASE;


    for (int i = 0; i < n; i++) {
        current_hash = current_hash * BASE + (B[i] - HASHER);
    }

    int cnt = 0;
    vector<int> positions;
    if (current_hash == hash_A) {
        cnt++;
        positions.push_back(0);
    }

    for (int i = n; i < m; i++) {
        current_hash = current_hash - (B[i - n] - HASHER) * power;
        current_hash = current_hash * BASE + (B[i] - HASHER);

        if (current_hash == hash_A) {
            positions.push_back(i - n + 1);
            cnt++;
        }
    }

    cout << cnt << '\n';
    for (int i = 0; i < min((int)positions.size(), 1000); i++) {
        cout << positions[i] <<' ';
    }
    return 0;
}