Cod sursa(job #3159507)

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