Cod sursa(job #1257387)

Utilizator xtreme77Patrick Sava xtreme77 Data 7 noiembrie 2014 18:28:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
/*
 * Code by Spiromanul
 */

#include <fstream>
#include <cstring>
#include <bitset>

const char IN  [ ] = "strmatch.in" ;
const char OUT [ ] = "strmatch.out" ;

const int MAX = 2000014 ;
const int MOD1 = 299777 ;
const int MOD2 = 299771 ;
const int Bb = 71 ;

using namespace std;

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

char A [ MAX ] , B [ MAX ] ;
bitset < MAX > ANS ;

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

    int SOL = 0 ;
    if ( SMALLHASH1 == BIGHASH1 and SMALLHASH2 == BIGHASH2 )
    {
        ANS [ 0 ] = 1 ;
        ++ SOL ;
    }
    for ( int i = NA ; i < NB ; ++ i )
    {
        BIGHASH1  = ( ( ( BIGHASH1 - B [ i - NA ] * PUTMAX1 ) % MOD1 + MOD1 ) * Bb + B [ i ] ) % MOD1 ;
        BIGHASH2  = ( ( ( BIGHASH2 - B [ i - NA ] * PUTMAX2 ) % MOD2 + MOD2 ) * Bb + B [ i ] ) % MOD2 ;
        if ( SMALLHASH1 == BIGHASH1 and SMALLHASH2 == BIGHASH2 )
        {
            ANS [ i - NA + 1 ] = 1 ;
            ++ SOL ;
        }
    }
    // afisare
    fout << SOL << '\n' ;
    SOL = 0 ;
    for ( int i = 0 ; i < NB and SOL <= 1000 ; ++ i )
        if ( ANS [ i ] )
        {
            fout << i << ' ' ;
            ++ SOL ;
        }
    fout << '\n' ;
    return 0;
}