Cod sursa(job #3328378)

Utilizator marctudor_ghenceaMarc-Tudor Ghencea marctudor_ghencea Data 8 decembrie 2025 11:12:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 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 rez = 0;

    int p1 = 1;
    int p2 = 1;

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

        nrb1 = (nrb1 * 73 + B[i]) % MOD1;
        nrb2 = (nrb2 * 73 + B[i]) % MOD2;
    }

    /*
    cout << "nra1 = " << nra1 << "\n";
    cout << "nra2 = " << nra2 << "\n";
    */

    for(int i = 1; i <= nrca - 1; i++){
        p1 = (p1 * 73) % MOD1;
        p2 = (p2 * 73) % MOD2;
    }

    if(nra1 == nrb1 && nra2 == nrb2){
        poz[++rez] = 0;
    }

    for(int i = 0; i <= nrcb - nrca - 1; i++){
        nrb1 = ((nrb1 - (B[i] * p1)) % MOD1 + MOD1) % MOD1;
        nrb1 = (nrb1 * 73) % MOD1;
        nrb1 += B[i + nrca];
        nrb1 %= MOD1;

        nrb2 = ((nrb2 - (B[i] * p2)) % MOD2 + MOD2) % MOD2;
        nrb2 = (nrb2 * 73) % MOD2;
        nrb2 += B[i + nrca];
        nrb2 %= MOD2;

        /*
        cout << "nrb1 = " << nrb1 << "\n";
        cout << "nrb2 = " << nrb2 << "\n";
        */

        if(nra1 == nrb1 && nra2 == nrb2){
            poz[++rez] = i+1;
        }
    }

    cout << rez << "\n";

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

    return 0;
}