Cod sursa(job #3312775)

Utilizator David_Popa123Popa David Matei David_Popa123 Data 29 septembrie 2025 20:43:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

#define MOD 100007
#define MOD2 100021
#define BAZA 62

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

string a, b;
vector<int> ans;

int main() {
    int n, m, i, b1, b2, hashA, hashA2, hashB, hashB2;

    fin >> a >> b;

    n = a.size();
    m = b.size();

    b1 = b2 = 1;
    hashA = hashA2 = 0;
    for( i = 0; i < n; i++ ) {
        hashA = ( hashA * BAZA + a[i] ) % MOD;
        hashA2 = ( hashA2 * BAZA + a[i] ) % MOD2;
        if( i > 0 ) {
            b1 = b1 * BAZA % MOD;
            b2 = b2 * BAZA % MOD2;
        }
    }

    hashB = hashB2 = 0;
    for( i = 0; i < n; i++ ) {
        hashB = ( hashB * BAZA + b[i] ) % MOD;
        hashB2 = ( hashB2 * BAZA + b[i] ) % MOD2;
    }

    if( hashA == hashB && hashA2 == hashB2 )
        ans.push_back(0);

    for( i = n; i < m; i++ ) {
        hashB = ( ( hashB - ( b[i - n] * b1 ) % MOD + MOD ) * BAZA + b[i] ) % MOD;
        hashB2 = ( ( hashB2 - ( b[i - n] * b2 ) % MOD2 + MOD2 ) * BAZA + b[i] ) % MOD2;
        if( hashA == hashB && hashA2 == hashB2 )
            ans.push_back(i - n + 1);
    }

    fout << ans.size() << '\n';
    for( int x : ans )
        fout << x << ' ';
    return 0;
}