Cod sursa(job #3318141)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 27 octombrie 2025 12:22:51
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 2000005;
const long long BASE = 100;
const long long MOD = 1000000007;
const char HASHER = '0';

char A[NMAX], B[NMAX];
long long powers[NMAX];

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

void PrecomputePowers(int n) {
    powers[0] = 1;
    for (int i = 1; i <= n; i++)
        powers[i] = (powers[i - 1] * BASE) % MOD;
}

long long HashEntireString(const char s[], int n) {
    long long h = 0;
    for (int i = 0; i < n; i++)
        h = (h * BASE + (s[i] - HASHER)) % MOD;
    return h;
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> A >> B;

    int n = strlen(A), m = strlen(B);
    if (m < n) {
        fout << 0 << "\n";
        return 0;
    }

    PrecomputePowers(n);


    long long hash_A = HashEntireString(A, n);


    vector<long long> prefix(m + 1, 0);
    for (int i = 0; i < m; i++)
        prefix[i + 1] = (prefix[i] * BASE + (B[i] - HASHER)) % MOD;

    vector<int> positions;

    
    for (int i = 0; i + n <= m; i++) {
        long long current_hash = (prefix[i + n] - prefix[i] * powers[n]) % MOD;
        if (current_hash < 0) current_hash += MOD;
        if (current_hash == hash_A)
            positions.push_back(i);
    }

    fout << positions.size() << "\n";
    for (int i = 0; i < min((int)positions.size(), 1000); i++)
        fout << positions[i] << " ";
    fout << "\n";

    return 0;
}