Cod sursa(job #3162108)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 28 octombrie 2023 13:07:04
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 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 n, hsh1, hsh2;
void hashuri( string &X ){
    hsh1 = 0, hsh2 = 0;
    for( int i = 0; i < A.size(); i++ ){
        hsh1 = (hsh1 * BAZA + X[i] - 'A'+1) % MOD1;
        hsh2 = (hsh2 * BAZA + X[i] - 'A'+1) % MOD2;
    }
}
int Putere( int a , int x , int mod ){
    if( x == 0 )
        return 1;
    if( x % 2 == 1)
        return ((long long)a * Putere(a , x - 1, mod)) % mod;
    int P = Putere(a , x / 2, mod) % mod;
    return ((long long)P * P)% mod;
}
int modif( int Hash, int i, int put, int mod ){
    Hash = ( Hash + mod - put * ( B[i-n] - 'A' + 1 ) ) % mod;
    Hash = ( Hash * BAZA + B[i] - 'A' + 1) % mod;
    return Hash;
}
int main()
{
    int rez = 0;
    vector <int> sol;
    in >> A >> B;
    n = A.size();
    hashuri(A);
    int Ahash1 = hsh1, Ahash2 = hsh2;
    hashuri(B);
    int Bhash1 = hsh1, Bhash2 = hsh2;
    int put1 = Putere( BAZA, n-1, MOD1);
    int put2 = Putere( BAZA, n-1, MOD2);
    if( Ahash1 == Bhash1 && Ahash2 == Bhash2){
        rez++;
        sol.push_back(0);
    }
    for( int i = n; i < B.size(); i++ ){
        Bhash1 = modif( Bhash1, i, put1, MOD1);
        Bhash2 = modif( Bhash2, i, put2, MOD2);
        if( Ahash1 == Bhash1 && Ahash2 == Bhash2){
            rez++;
            sol.push_back(i-n+1);
        }
    }
    out << rez << "\n";
    int k = sol.size();
    if( k > 1000 )
        k = 1000;
    for( int i = 0; i < k; i++ )
        out << sol[i] << " ";
    return 0;
}