Cod sursa(job #3328376)

Utilizator marctudor_ghenceaMarc-Tudor Ghencea marctudor_ghencea Data 8 decembrie 2025 10:35:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <cstring>

#define MOD1 100007
#define MOD2 100021

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

char A[2000001], B[2000001];
int poz[2000001];

int main()
{
    cin >> A;
    cin >> B;

    int nrca = strlen(A);
    int nrcb = strlen(B);

    if(nrca > nrcb){
        cout << "0\n";
        return 0;
    }

    int nra1 = 0;
    int nra2 = 0;
    int nrb1 = 0;
    int nrb2 = 0;

    int p = 1;

    int rez = 0;

    for(int i = 0; i < nrca; i++){
        nra1 += A[i] * 62 * p % MOD1;
        nra2 += A[i] * 62 * p % MOD2;

        nrb1 += B[i] * 62 * p % MOD1;
        nrb2 += B[i] * 62 * p % MOD2;

        p *= 62;
    }

    p /= 62;

    for(int i = 0; i <= nrcb - nrca - 1; i++){
        if(nra1 == nrb1 && nra2 == nrb2){
            poz[++rez] = i;
        }
        
        nrb1 = ((nrb1 % MOD1 - (B[i] * p) % MOD1) + MOD1) % MOD1;
        nrb1 *= 62;
        nrb1 += B[i+nrca];
        nrb1 %= MOD1;

        nrb2 = ((nrb2 % MOD2 - (B[i] * p) % MOD2) + MOD2) % MOD2;
        nrb2 *= 62;
        nrb2 += B[i+nrca];
        nrb2 %= MOD2;
    }

    cout << rez << "\n";

    for(int i = 1; i <= rez; i++){
        cout << poz[i] << " ";
    }
    cout << "\n";

    return 0;
}