Cod sursa(job #2623961)

Utilizator euyoTukanul euyo Data 4 iunie 2020 11:42:02
Problema Potrivirea sirurilor Scor 14
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#include <string.h>
#define MAXL 2000000
#define H1 32103110
#define H2 666013
#define BASE 127

char A[MAXL], B[MAXL];
int pos[MAXL], ap;

void verif( int p, int hA1, int hA2, int hB1, int hB2 ) {
  if ( hA1 == hB1 && hA2 == hB2 ) {
    pos[ap++] = p;
  }
}

int main() {
  FILE *fin = fopen( "strmatch.in", "r" );
  FILE *fout = fopen( "strmatch.out", "w" );
  int i, lA, lB, hashA1 = 0, hashA2 = 0, hashB1 = 0, hashB2 = 0, basep1 = 1, basep2 = 1;
  
  fscanf( fin, "%s%s", A, B );
  lA = strlen( A );
  lB = strlen( B );
  for ( i = 0; i < lA; ++i ) {
	hashA1 = (A[i] + hashA1 * BASE) % H1;
	hashA2 = (A[i] + hashA2 * BASE) % H2;
	if ( i != 0 ) {
	  basep1 = (basep1 * BASE) % H1;
	  basep2 = (basep2 * BASE) % H2;
    }
  }
  for ( i = 0; i < lA; ++i ) {
	hashB1 = (B[i] + hashB1 * BASE) % H1;
	hashB2 = (B[i] + hashB2 * BASE) % H2;
  }
  verif( 0, hashA1, hashA2, hashB1, hashB2 );
  for ( i = lA; i < lB; ++i ) {
	hashB1 = (((hashB1 - (basep1 * B[i - lA]) % H1 + H1) % H1) * BASE + B[i]) % H1;
    hashB2 = (((hashB2 - (basep2 * B[i - lA]) % H2 + H2) % H2) * BASE + B[i]) % H2;
	verif( i - lA + 1, hashA1, hashA2, hashB1, hashB2 );
  }
  fprintf( fout, "%d\n", ap );
  for ( i = 0; i < ap; ++i ) {
	fprintf( fout, "%d ", pos[i] );
  }
  fclose( fin );
  fclose( fout );
  return 0;
}