Cod sursa(job #3162121)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 28 octombrie 2023 13:31:26
Problema Potrivirea sirurilor Scor 92
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;
const int BAZA = 37;
const int MOD1 = 666013;
const int MOD2 = 511111;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string A, B;

int modif( int Hash, int i, int put, int mod ){
    Hash = ( Hash + mod - ( put * ( B[i - (int)A.size()] - 'A' + 1 )) % mod ) % mod;
    Hash = ( Hash * BAZA + B[i] - 'A' + 1) % mod;
    return Hash;
}
int main()
{
    int Ahash1, Ahash2, Bhash1, Bhash2, put1 = 1, put2 = 1;
    vector <int> sol;
    in >> A >> B;
    if( A.size() == B.size()){
        out << 0;
        return 0;
    }
    Ahash1 = Ahash2 = Bhash1 = Bhash2 = 0;
    for( int i = 0; i < A.size(); i++ ){
        Ahash1 = (Ahash1 * BAZA + A[i] - 'A' + 1 ) % MOD1;
        Ahash2 = (Ahash2 * BAZA + A[i] - 'A' + 1 ) % MOD2;
        if( i ){
            put1 = ( put1 * BAZA ) % MOD1;
            put2 = ( put2 * BAZA ) % MOD2;
        }
    }
    for( int i = 0; i < A.size(); i++ ){
        Bhash1 = (Bhash1 * BAZA + B[i] - 'A' + 1 ) % MOD1;
        Bhash2 = (Bhash2 * BAZA + B[i] - 'A' + 1 ) % MOD2;
    }
    if( Ahash1 == Bhash1 && Ahash2 == Bhash2)
        sol.push_back(0);

    for( int i = A.size(); i < B.size(); i++ ){
        Bhash1 = modif( Bhash1, i, put1, MOD1);
        Bhash2 = modif( Bhash2, i, put2, MOD2);
        if( Ahash1 == Bhash1 && Ahash2 == Bhash2)
            sol.push_back(i-A.size()+1);
    }
    out << sol.size() << "\n";
    int k = sol.size();
    if( k > 1000 )
        k = 1000;
    for( int i = 0; i < k; i++ )
        out << sol[i] << " ";
    return 0;
}