Cod sursa(job #1915237)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 8 martie 2017 20:17:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 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 valk1, valk2;
    int hash1, hash2;

    hash1 = hash2 = 0;
    valk1 = valk2 = 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 ) {
        valk1 = ( valk1 * BAZA + A[ i ] ) % MOD1;
        valk2 = ( valk2 * BAZA + A[ i ] ) % MOD2;

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

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

    if ( hash1 == valk1 && hash2 == valk2 ) Q.push( 0 );

    for ( i = n; i < m; ++i ) {
        hash1 = ( ( hash1 - ( B[ i - n ] * p1 ) % MOD1 + MOD1 ) * BAZA + B[ i ] ) % MOD1;
        hash2 = ( ( hash2 - ( B[ i - n ] * p2 ) % MOD2 + MOD2 ) * BAZA + B[ i ] ) % MOD2;
            if ( hash1 == valk1 && hash2 == valk2 )
                Q.push( i - n + 1 );
    }

    printf( "%d\n",Q.size() );
    m = 0;
    while ( !Q.empty() && m < 1000 ) {
        printf( "%d ",Q.front() );
        Q.pop();
        m++;
    }

    return 0;

}