Cod sursa(job #1583451)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 28 ianuarie 2016 23:10:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <cstring>


const int VAL1 = 23;
const int VAL2 = 29;
const int MOD1 = 100007;
const int MOD2 = 100021;
const int DIM  = 1 << 21;
const int DIM2 = 1 << 10;

int N, M, K; char A[DIM], B[DIM];
int hash1, hash2, exp1 = 1, exp2 = 1;
int value1, value2, Answer[DIM2];

int main () {

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

    scanf( "%s %s", A, B );
    N = strlen( A );
    M = strlen( B );

    for( int i = 0; i < N; i ++ ) {
        hash1 = (hash1 * VAL1 + A[i]) % MOD1;
        hash2 = (hash2 * VAL2 + A[i]) % MOD2;

        if( i ) {
            exp1 = (exp1 * VAL1) % MOD1;
            exp2 = (exp2 * VAL2) % MOD2;
        }
    }

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

    for( int i = 0; i < N; i ++ ) {
        value1 = (value1 * VAL1 + B[i]) % MOD1;
        value2 = (value2 * VAL2 + B[i]) % MOD2;
    }

    if( value1 == hash1 && value2 == hash2 )
        Answer[++K] = 0;

    for( int i = N; i < M; i ++ ) {
        value1 = ((value1 - (B[i - N] * exp1) % MOD1 + MOD1) * VAL1 + B[i]) % MOD1;
        value2 = ((value2 - (B[i - N] * exp2) % MOD2 + MOD2) * VAL2 + B[i]) % MOD2;

        if( value1 == hash1 && value2 == hash2 ) {
            K ++;
            if( K <= 1000 )
                Answer[K] = i - N + 1;
        }
    }

    printf( "%d\n", K );
    for( int i = 1; i <= K && i <= 1000; i ++ )
        printf( "%d ", Answer[i] );

    return 0;
}