Cod sursa(job #2795170)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 6 noiembrie 2021 00:56:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
// Mihai Priboi

#include <bits/stdc++.h>

#define HASHSIZE1 1000003
#define HASHSIZE2 666013
#define HASHBASE1 511
#define HASHBASE2 255
#define MAXLEN 2000002
#define MAXRASP 1000

char v[MAXLEN];
int rasp[MAXRASP];

int getHash( int first, int size, int hashbase, int hashsize ) {
  int rez, i;

  rez = 0;
  for( i = first; i < first + size; i++ )
    rez = ( rez * hashbase + v[i] ) % hashsize;

  return rez;
}

void shiftHash( int &hash, char ch1, char ch2, int hashbase, int hashbasepow, int hashsize ) {
  // stergem primul element
  hash -= ch1 * hashbasepow % hashsize;
  hash += hash < 0 ? hashsize : 0;
  // adaugam un element la final
  hash = ( hash * hashbase + ch2 ) % hashsize;
}

int main() {
  FILE *fin, *fout;
  char ch;
  int na, nb, hash1, hash2, hashbasepow1, hashbasepow2, a_hash1, a_hash2, cnt, i;

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

  fgets( v, MAXLEN, fin );
  na = strlen(v) - 1;

  a_hash1 = getHash( 0, na, HASHBASE1, HASHSIZE1 );
  a_hash2 = getHash( 0, na, HASHBASE2, HASHSIZE2 );

  fgets( v, MAXLEN, fin );
  nb = strlen(v) - 1;

  fclose( fin );

  hash1 = getHash( 0, na, HASHBASE1, HASHSIZE1 );
  hash2 = getHash( 0, na, HASHBASE2, HASHSIZE2 );

  hashbasepow1 = hashbasepow2 = 1;
  for( i = 1; i < na; i++ ) {
    hashbasepow1 = hashbasepow1 * HASHBASE1 % HASHSIZE1;
    hashbasepow2 = hashbasepow2 * HASHBASE2 % HASHSIZE2;
  }

  cnt = 0;

  for( i = 0; i < nb - na + 1; i++ ) {
    if( i > 0 ) {
      shiftHash( hash1, v[i - 1], v[i + na - 1], HASHBASE1, hashbasepow1, HASHSIZE1 );
      shiftHash( hash2, v[i - 1], v[i + na - 1], HASHBASE2, hashbasepow2, HASHSIZE2 );
    }

    if( hash1 == a_hash1 && hash2 == a_hash2 ) {
      if( cnt < MAXRASP )
        rasp[cnt] = i;
      cnt++;
    }
  }

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

  fprintf( fout, "%d\n", cnt );
  for( i = 0; i < std::min( cnt, MAXRASP ); i++ )
    fprintf( fout, "%d ", rasp[i] );

  fclose( fout );
  return 0;
}