Cod sursa(job #2796569)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 8 noiembrie 2021 14:38:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <stdio.h>
#include <string.h>

#define LUNGMAXX 2000000
#define BAZAHASH 256
#define MOD1 666031
#define MOD2 1000007
#define POZMAXX 1000

using namespace std;

char sirA[LUNGMAXX + 1], sirB[LUNGMAXX + 1];
int poz[POZMAXX], lungA, lungB;

int main() {
    FILE *fin, *fout;
    int i, pHash1, pHash2, hash1, hash2, pow1, pow2, cnt;

    fin = fopen( "strmatch.in", "r" );
    fout = fopen( "strmatch.out", "w" );

    fgets( sirB, sizeof( sirB ), fin );
    lungB = strlen( sirB );
    if ( sirB[lungB - 1] == '\n' )
        sirB[--lungB] = 0;

    fgets( sirA, sizeof( sirA ), fin );
    lungA = strlen( sirA );
    if ( sirA[lungA - 1] == '\n' )
        sirA[--lungA] = 0;

    pHash1 = pHash2 = hash1 = hash2 = 0;
    pow1 = pow2 = 1;
    for ( i = 0; i < lungB; i++ ) {
        pHash1 = ( pHash1 * BAZAHASH + sirB[i] ) % MOD1;
        pHash2 = ( pHash2 * BAZAHASH + sirB[i] ) % MOD2;

        hash1 = ( hash1 * BAZAHASH + sirA[i] ) % MOD1;
        hash2 = ( hash2 * BAZAHASH + sirA[i] ) % MOD2;

        if ( i > 0 ) {
            pow1 = ( pow1 * BAZAHASH ) % MOD1;
            pow2 = ( pow2 * BAZAHASH ) % MOD2;
        }
    }

    cnt = 0;
    i = lungB;
    while ( i <= lungA ) {
        if ( hash2 == pHash2 && hash1 == pHash1 ) {
            if ( cnt < POZMAXX )
                poz[cnt] = i - lungB;
            cnt++;
        }

        hash1 -= sirA[i - lungB] * pow1 % MOD1;
        if ( hash1 < 0 )
            hash1 += MOD1;

        hash2 -= sirA[i - lungB] * pow2 % MOD2;
        if ( hash2 < 0 )
            hash2 += MOD2;

        hash1 = ( hash1 * BAZAHASH + sirA[i] ) % MOD1;
        hash2 = ( hash2 * BAZAHASH + sirA[i] ) % MOD2;

        i++;
    }

    fprintf( fout, "%d\n", cnt );
    for ( i = 0; i < cnt && i < POZMAXX; i++ ) {
        fprintf( fout, "%d ", poz[i] );
    }

    fclose( fin );
    fclose( fout );
    return 0;
}