Cod sursa(job #1262481)

Utilizator AndreiBarbutaAndrei Barbuta AndreiBarbuta Data 13 noiembrie 2014 11:23:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <cstring>

#define IN "strmatch.in"
#define OUT "strmatch.out"

const int MAX = 2000014 ;
const int P = 57 ;
const int MOD1 = 666013 ;
const int MOD2 = 666017 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

char A [ MAX ] , B [ MAX ] ;
int ans [ MAX ] ;

int main()
{
    int NA , NB , SMALLHASH1 = 0 , BIGHASH1 = 0 , SMALLHASH2 = 0 , BIGHASH2 = 0 , PUTMAX1 = 1 , PUTMAX2 = 1 ;
    fin >> A ;
    fin >> B ;
    NA = strlen ( A ) ;
    NB = strlen ( B ) ;
    if ( NA > NB ){
        fout << "0" ;
        return  0 ;
    }
    for ( register int i = 0 ; i < NA ; ++ i ){
        SMALLHASH1 = ( SMALLHASH1 * P + A [ i ] ) % MOD1 ;
        SMALLHASH2 = ( SMALLHASH2 * P + A [ i ] ) % MOD2 ;
        if ( i ){
            PUTMAX1 = ( PUTMAX1 * P ) % MOD1 ;
            PUTMAX2 = ( PUTMAX2 * P ) % MOD2 ;
        }
    }
    int sol = 0 ;
    for ( register int i = 0 ; i < NA ; ++ i ){
        BIGHASH1 = ( BIGHASH1 * P + B [ i ] ) % MOD1 ;
        BIGHASH2 = ( BIGHASH2 * P + B [ i ] ) % MOD2 ;
    }
    if ( BIGHASH1 == SMALLHASH1 and BIGHASH2 == SMALLHASH2 )
        ans [ ++ sol ] = 0 ;
    for ( register int  i = NA ; i < NB ; ++ i ){
        BIGHASH1 = ( ( ( ( BIGHASH1 - B [ i - NA ] * PUTMAX1 ) % MOD1 + MOD1 ) * P ) + B [ i ] ) % MOD1 ;
        BIGHASH2 = ( ( ( ( BIGHASH2 - B [ i - NA ] * PUTMAX2 ) % MOD2 + MOD2 ) * P ) + B [ i ] ) % MOD2 ;
        if ( BIGHASH1 == SMALLHASH1 and BIGHASH2 == SMALLHASH2 )
            ans [ ++ sol ] = i - NA + 1 ;
    }
    fout << sol << '\n' ;
    if ( sol > 1000 )
        for ( sol = 1 ; sol < 1000 ; ++ sol  )
            fout << ans [ sol ] << " " ;
    else
        for ( register int  i = 1 ; i <= sol ; ++ i )
            fout << ans [ i ] << " " ;
    return 0;
}