Cod sursa(job #3333370)

Utilizator Calin2009Gae Mihai Calin Calin2009 Data 13 ianuarie 2026 10:44:50
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007;
static const long long BASE = 131;

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

    string A, B;
    fin >> A >> B;

    int n = A.size();
    int m = B.size();

    if (n > m) {
        fout << 0 << "\n";
        return 0;
    }

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

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

    long long hashA = 0;
    for (char c : A)
        hashA = (hashA * BASE + c) % MOD;

    vector<int> positions;

    for (int i = 0; i + n <= m; i++) {
        long long currentHash =
            (hashB[i + n] - (hashB[i] * power[n]) % MOD + MOD) % MOD;

        if (currentHash == hashA) {
            if (B.substr(i, n) == A) {
                positions.push_back(i);
            }
        }
    }

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

    return 0;
}