Cod sursa(job #3312778)

Utilizator David_Popa123Popa David Matei David_Popa123 Data 29 septembrie 2025 20:50:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 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);
    }

    if( ans.size() < 1000 ) {
        fout << ans.size() << '\n';
        for( int x : ans )
            fout << x << ' ';
    } else {
        fout << ans.size() << '\n';
        for( i = 0; i < 1000; i++ )
            fout << ans[i] << ' ';
    }
    return 0;
}