Cod sursa(job #2545612)

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

using namespace std ;

const long long MOD1 = 1e9 + 7 ;
const long long MOD2 = 1e9 + 9 ;
const long long BASE = 91 ;
vector < int > v ;

inline long long fast_pow ( long long x , long long y , long long mod )
{
    long long ans = 1 , p = x ;

    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 hash11 , hash12 , hash21 , hash22 ;
    long long i , n , m , inv1 , inv2 , pwr1 , pwr2 ;

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

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

    inv1 = fast_pow ( BASE , MOD1 - 2 , MOD1 ) ;
    inv2 = fast_pow ( BASE , MOD2 - 2 , MOD2 ) ;

    hash11 = hash12 = hash21 = hash22 = 0 ; pwr1 = pwr2 = 1 ;

    for ( i = 0 ; i < n ; ++ i )
    {
        hash11 = ( hash11 + ( pwr1 * 1LL * inp1 [ i ] ) % MOD1 ) % MOD1 ;
        hash21 = ( hash21 + ( pwr1 * 1LL * inp2 [ i ] ) % MOD1 ) % MOD1 ;
        pwr1 = ( pwr1 * BASE ) % MOD1 ;

        hash12 = ( hash12 + ( pwr2 * 1LL * inp1 [ i ] ) % MOD2 ) % MOD2 ;
        hash22 = ( hash22 + ( pwr2 * 1LL * inp2 [ i ] ) % MOD2 ) % MOD2 ;
        pwr2 = ( pwr2 * BASE ) % MOD2 ;
    }

    if ( hash11 == hash21 && hash12 == hash22 )
        v.push_back ( 0 ) ;

    pwr1 = fast_pow ( BASE , n - 1 , MOD1 ) ;
    pwr2 = fast_pow ( BASE , n - 1 , MOD2 ) ;

    for ( i = n ; i < m ; ++ i )
    {
        hash21 = ( hash21 + MOD1 - inp2 [ i - n ] ) % MOD1 ;
        hash21 = ( hash21 * inv1 ) % MOD1 ;
        hash21 = ( hash21 + ( 1LL * inp2 [ i ] * pwr1 ) % MOD1 ) % MOD1 ;

        hash22 = ( hash22 + MOD2 - inp2 [ i - n ] ) % MOD2 ;
        hash22 = ( hash22 * inv2 ) % MOD2 ;
        hash22 = ( hash22 + ( 1LL * inp2 [ i ] * pwr2 ) % MOD2 ) % MOD2 ;

        if ( hash11 == hash21 && hash12 == hash22 && v.size () < 1000 )
            v.push_back ( i - n + 1 ) ;
    }

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

    return 0 ;
}