Cod sursa(job #2545533)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 13 februarie 2020 11:26:30
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.78 kb
#include <cmath>
#include <vector>
#include <fstream>
#include <iostream>

using namespace std ;

string inp1 , inp2 ;


inline long long fast_pow ( int x , int y , int mod )
{
    if ( y == 1 ) return x ;

    long long p = x , ans = 1 ;

    while ( y )
    {
        if ( y & 1 )
            ans = ( ans * p ) % mod ;
        p = ( p * p ) % mod ;
        y = ( y >> 1 ) ;
    }

    return ans ;
}

struct hash_pair
{
    long long hash1 , hash2 , BASE , MOD , INV_MOD , p ;

    void hardcode ( long long a , long long b )
    {
        BASE = a ;
        MOD = b ;
        INV_MOD = fast_pow ( BASE , MOD - 2 , MOD ) ;
    }
} ;

hash_pair hash_array [ 10 ] ;
int nr = 0 ;
vector < long long > v ;

int main ()
{
    ifstream in ( "strmatch.in" ) ;
    ofstream out ( "strmatch.out" ) ;

    int i , j , mod , pwr , base , n , m , ok ;

    nr = 2 ;
    hash_array [ 1 ].hardcode ( 1e4 + 39 , 1e9 + 9 ) ;
    hash_array [ 2 ].hardcode ( 1e4 + 61 , pow ( 2 , 31 ) - 1 ) ;

    in >> inp1 >> inp2 ;

    n = inp1.size () ;
    m = inp2.size () ;

    if ( n > m )
    {
        out << "0" ;
        return 0 ;
    }

    for ( i = 1 ; i <= nr ; ++ i )
        hash_array [ i ].p = 1 ;

    for ( i = 0 ; i < n ; ++ i )
        for ( j = 1 ; j <= nr ; ++ j )
        {
            mod = hash_array [ j ].MOD ; pwr = hash_array [ j ].p ; base = hash_array [ j ].BASE ;
            hash_array [ j ].hash1 = ( hash_array [ j ].hash1 + ( 1LL * inp1 [ i ] * pwr ) % mod ) % mod ;
            hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + ( 1LL * inp2 [ i ] * pwr ) % mod ) % mod ;
            pwr = ( pwr * base ) % mod ;
            hash_array [ j ].p = pwr ;
        }

    for ( i = 1 ; i <= nr ; ++ i )
        hash_array [ i ].p = fast_pow ( hash_array [ i ].BASE , n - 1 , hash_array [ i ].MOD ) ;

    ok = 1 ;
    for ( i = 1 ; i <= nr ; ++ i )
        if ( hash_array [ i ].hash1 != hash_array [ i ].hash2 )
        {
            ok = 0 ;
            break ;
        }

    if ( ok ) v.push_back ( 0 ) ;

    for ( i = 1 ; i < m - n + 1 ; ++ i )
    {
        ok = 1 ;

        for ( j = 1 ; j <= nr ; ++ j )
        {
            mod = hash_array [ j ].MOD ; base = hash_array [ j ].BASE ; pwr = hash_array [ j ].p ;
            hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + mod - inp2 [ i - 1 ] ) % mod ;
            hash_array [ j ].hash2 = ( hash_array [ j ].hash2 * hash_array [ j ].INV_MOD ) % mod ;
            hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + ( 1LL * inp2 [ i + n - 1 ] * pwr ) % mod ) % mod ;

            if ( hash_array [ j ].hash1 != hash_array [ j ].hash2 )
                ok = 0 ;
        }

        if ( ok && v.size () < 1000 )
            v.push_back ( i ) ;
    }

    out << v.size () << '\n' ;
    for ( i = 0 ; i < v.size () ; ++ i )
        out << v [ i ] << ' ' ;

    return 0 ;
}