Cod sursa(job #2792830)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 2 noiembrie 2021 12:46:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <stdio.h>
#include <string.h>

#define LMAXX 2000000
#define HASHSIZE 666013
#define BAZAHASH 256
#define POZMAXX 1000

using namespace std;

FILE *fin, *fout;
char sirA[LMAXX + 1], sirB[LMAXX + 1];
int poz[POZMAXX], lungA, lungB;

int put( int a, int n ) {
    int p;

    p = 1;
    while( n ) {
        if ( n % 2 == 1 )
            p = (long long)p * a % HASHSIZE;

        a = (long long)a * a % HASHSIZE;
        n /= 2;
    }

    return p;
}

int computeHash( char v[], int size ) {
    int hash, i;

    hash = i = 0;
    while ( i < size ) {
        hash = ( hash * BAZAHASH + v[i] ) % HASHSIZE;
        i++;
    }

    return hash;
}

int add( char ch, int hash ) {
    return ( hash * BAZAHASH + ch ) % HASHSIZE;
}

int erase( char ch, int hash, int pow ) {
    hash -= ch * pow % HASHSIZE;
    if ( hash < 0 ) {
        hash += HASHSIZE;
    }

    return hash;
}

void afis( int n ) {
    int i;

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

bool cmp( char v1[], char v2[] ) {
    int i;

    i = 0;
    while ( v1[i] && v2[i] && v1[i] == v2[i] )
        ++i;

    return v2[i] == 0;
}

void search( char v1[], int size1, char v2[], int size2 ) {
    int i, hashA, hashB, pow, cnt;

    hashB = computeHash( v2, size2 );
    hashA = computeHash( v1, size1 );

    pow = put( BAZAHASH, size2 - 1 );

    cnt = 0;
    i = size2;
    while ( i <= size1 ) {
        hashA = add( v1[i - 1], hashA );
        if ( cmp( v1 + i - size2, v2 ) ) {
            poz[cnt] = i - size2;
            cnt++;
        }

        hashA = erase( v1[i - 1], hashA, pow );
        i++;
    }

    afis( cnt );
}

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

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

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

    fclose( fin );

    search( sirA, lungA, sirB, lungB );
    fclose( fout );
    return 0;
}