Cod sursa(job #2623980)

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

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

static inline void verif( unsigned p, unsigned hA1, unsigned hA2, unsigned hB1, unsigned hB2 ) {
  if ( hA1 == hB1 && hA2 == hB2 && ap < 1000 ) {
    pos[ap++] = p;
  }
}

unsigned cod(char ch) {
	if ('a' <= ch && ch <= 'z') {
		return ch - 'a';
	}
	if ('A' <= ch && ch <= 'Z') {
		return ch - 'A' + 26;
	}
	return ch - '0' + 52;
}

int main() {
  FILE *fin = fopen( "strmatch.in", "r" );
  FILE *fout = fopen( "strmatch.out", "w" );
  int i, lA, lB;
  unsigned 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 = (cod(A[i]) + hashA1 * BASE) % H1;
	hashA2 = (cod(A[i]) + hashA2 * BASE) % H2;
	if ( i != 0 ) {
	  basep1 = (basep1 * BASE) % H1;
	  basep2 = (basep2 * BASE) % H2;
    }
  }
  for ( i = 0; i < lA; ++i ) {
	hashB1 = (cod(B[i]) + hashB1 * BASE) % H1;
	hashB2 = (cod(B[i]) + hashB2 * BASE) % H2;
  }
  verif( 0, hashA1, hashA2, hashB1, hashB2 );
  for ( i = lA; i < lB; ++i ) {
	if ( ap < 1000 ) {
	  hashB1 = (((hashB1 + H1 - (basep1 * cod(B[i - lA])) % H1) % H1) * BASE + cod(B[i])) % H1;
      hashB2 = (((hashB2 + H2 - (basep2 * cod(B[i - lA])) % H2) % H2) * BASE + cod(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;
}