Cod sursa(job #2545468)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 13 februarie 2020 09:53:59
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cmath>
#include <vector>
#include <fstream>
#include <iostream>

using namespace std;

const int BASE = 2 ;
const int MOD = pow ( 2 , 31 ) - 1 ;
vector < int > v ;

inline int 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 ;
}

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

    string inp1 , inp2 ;
    long long hash1 = 0 , hash2 = 0 , p , inv = fast_pow ( BASE , MOD - 2 , MOD ) , i ;

    in >> inp1 >> inp2 ;

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

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

    p = fast_pow ( BASE , inp1.size () - 1 , MOD ) ;

    if ( hash1 == hash2 )
        v.push_back ( 0 ) ;

    for ( i = 1 ; i < inp2.size () ; ++ i )
    {
        hash2 -= inp2 [ i - 1 ] ;
        if ( hash2 < 0 ) hash2 += MOD ;

        hash2 = ( hash2 * inv ) % MOD ;
        hash2 = ( hash2 + p * inp2 [ i + inp1.size () - 1 ] ) % MOD ;

        if ( hash2 == hash1 && v.size () < 1000 )
            v.push_back ( i ) ;
    }

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

    return 0;
}