Cod sursa(job #3279861)

Utilizator Dragu_AndiDragu Andrei Dragu_Andi Data 24 februarie 2025 16:34:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int MOD = 1000000007, BASE = 256;
int a, b;
string A, B;
vector<int> matches;

// Modular exponentiation to compute BASE^(a-1) % MOD
long long modPow(int base, int exp, int mod) {
    long long result = 1, power = base;
    while (exp) {
        if (exp % 2)
            result = (result * power) % mod;
        power = (power * power) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    fin >> A >> B;
    a = A.size();
    b = B.size();

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

    int hashA = 0, curHashB = 0;
    long long maxBaseInMod = modPow(BASE, a - 1, MOD);

    // Compute initial hashes
    for (int i = 0; i < a; i++) {
        hashA = (hashA * BASE + A[i]) % MOD;
        curHashB = (curHashB * BASE + B[i]) % MOD;
    }

    // Sliding window hash matching
    for (int i = a; i <= b; i++) {
        if (hashA == curHashB && A == B.substr(i - a, a))
            matches.push_back(i - a);

        if (i < b) {
            curHashB = (curHashB - (maxBaseInMod * B[i - a]) % MOD + MOD) % MOD;
            curHashB = (curHashB * BASE + B[i]) % MOD;
        }
    }

    // Output results
    fout << matches.size() << '\n';
    for (size_t i = 0; i < min(matches.size(), (size_t)1000); i++)
        fout << matches[i] << ' ';

    return 0;
}