Cod sursa(job #1915176)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 8 martie 2017 20:04:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

#define NMAX 2000002
#define MOD1 100007
#define MOD2 100021
#define BAZA 73

char A[ NMAX ];
char B[ NMAX ];
queue < int > Q;

int main () {

    freopen( "strmatch.in", "r", stdin );
    freopen( "strmatch.out", "w", stdout );

    int n, m, i, j, x, y, p1, p2;

    int cod_sablon1, cod_sablon2;
    int cod_cautare1, cod_cautare2;

    cod_cautare1 = cod_cautare2 = 0;
    cod_sablon1 = cod_sablon2 = 0;
    p1 = p2 = 1;

    scanf( "%s%s",&A,&B );

    n = strlen( A );
    m = strlen( B );

    if ( n > m ) {
        printf( "0\n" );
        return 0;
    }

    for ( i = 0; i < n; ++i ) {
        cod_sablon1 = ( cod_sablon1 * BAZA + A[ i ] ) % MOD1;
        cod_sablon2 = ( cod_sablon2 * BAZA + A[ i ] ) % MOD2;

        if ( i > 0 ) {
            p1 = ( p1 * BAZA ) % MOD1;
            p2 = ( p2 * BAZA ) % MOD2;
        }
    }

    for ( i = 0; i < n; ++i ) {
        cod_cautare1 = ( cod_cautare1 * BAZA + B[ i ] ) % MOD1;
        cod_cautare2 = ( cod_cautare2 * BAZA + B[ i ] ) % MOD2;
    }

    if ( cod_cautare1 == cod_sablon1 && cod_cautare2 == cod_sablon2 ) Q.push( 0 );

    for ( i = n; i <= m; ++i ) {
        cod_cautare1 = ( ( cod_cautare1 - B[ i - n ] * p1 % MOD1 + MOD1 ) * BAZA + B[ i ] ) % MOD1;
        cod_cautare2 = ( ( cod_cautare2 - B[ i - n ] * p2 % MOD2 + MOD2 ) * BAZA + B[ i ] ) % MOD2;
            if ( cod_cautare1 == cod_sablon1 && cod_cautare2 == cod_sablon2 ) Q.push( i - n + 1 );

    }

    printf( "%d\n",Q.size() );
    while ( !Q.empty() ) {
        printf( "%d ",Q.front() );
        Q.pop();
    }

    return 0;

}