Cod sursa(job #1262491)

Utilizator AndreiBarbutaAndrei Barbuta AndreiBarbuta Data 13 noiembrie 2014 11:34:44
Problema Potrivirea sirurilor Scor 14
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 = 113 ;
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 [ 0 ] = 1 ;
        sol ++ ;
    }
    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 ){
            sol ++ ;
            ans [ i - NA + 1 ] = 1;
        }
    }
    fout << sol << '\n' ;
    sol = 1 ;
    for ( register int  i = 1 ; i < NB and sol < 1000 ; ++ i )
        if ( ans [ i ] ){
            fout << i << " " ;
            sol ++ ;
        }
    return 0;
}