Cod sursa(job #2545511)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 13 februarie 2020 11:08:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 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 ;

inline int ok ( void )
{
    for ( int i = 1 ; i <= nr ; ++ i )
        if ( hash_array [ i ].hash1 != hash_array [ i ].hash2 )
            return 0 ;

    return 1 ;
}

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

    int i , j ;

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

    in >> inp1 >> inp2 ;

    if ( inp1.size () > inp2.size () )
    {
        out << "0" ;
        return 0 ;
    }

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

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

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

    if ( ok () )
        v.push_back ( 0 ) ;

    for ( i = 1 ; i < inp2.size () - inp1.size () + 1 ; ++ i )
    {
        for ( j = 1 ; j <= nr ; ++ j )
        {
            hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + hash_array [ j ].MOD - inp2 [ i - 1 ] ) % hash_array [ j ].MOD ;
            hash_array [ j ].hash2 = ( hash_array [ j ].hash2 * hash_array [ j ].INV_MOD ) % hash_array [ j ].MOD ;
            hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + inp2 [ i + inp1.size () - 1 ] * hash_array [ j ].p ) % hash_array [ j ].MOD ;
        }

        if ( ok () )
            v.push_back ( i ) ;
    }

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

    return 0 ;
}