Cod sursa(job #1523474)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 12 noiembrie 2015 19:20:38
Problema Potrivirea sirurilor Scor 14
Compilator c Status done
Runda Arhiva educationala Marime 1.68 kb
#include <stdio.h>
#include <string.h>
#define MAXLEN 2000000

char v1[MAXLEN];
char v2[MAXLEN];
char fvind[MAXLEN];
int pozsol[MAXLEN];
int pozsolfin[MAXLEN];
int modval[2] = { 1000003, 1000037 };

/// numarul initial, poz. de sters, poz. de adaugat, poz. modululului, puterea lui 123 maxima <= num
int pass ( int num, int i, int j, int x, int p123 ) { /// sterg ultima cifra si o adaug pe urmatoarea
  return ( ( num - v2[i] ) / 123 + v2[j] * p123 );// % modval[x];
}

int main () {
  FILE *fin, *fout;

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

  fscanf( fin, "%s%s", &v1, &v2 );

  int modnum, i, len = strlen ( v1 ), len2 = strlen( v2 ), p123 = 1, num1, num2; /// num1 in num2
  int cnt, max = 0; /// counter, nr. maxim al contorului, pozitia lui

  for ( modnum = 0; modnum < 2; modnum++ ) {
    num1 = num2 = 0;
    cnt = 0;

    p123 = 1;
    for ( i = 0; i < len; i++ ) {
      num1 = ( num1 + v1[i] * p123 );// % modval[modnum];
      num2 = ( num2 + v2[i] * p123 );// % modval[modnum];
      p123 = ( p123 * 123 );// % modval[modnum];
    }

    for ( i = len; i < len2; i++ ) {
      if ( num1 == num2 && cnt < 1000 )
        pozsol[cnt++] = i - len;

      p123 = 1;
      while ( p123 * 123 <= num2 )
        p123 *= 123;

      num2 = pass ( num2, i - len, i, modnum, p123 );
    }

    fvind[cnt] += ( cnt > 0 );

    if ( fvind[cnt] > fvind[max] ) {
      max = cnt;
      for ( i = 0; i < cnt; i++ )
        pozsolfin[i] = pozsol[i];
    }
  }

  fprintf( fout, "%d\n", max );
  for ( i = 0; i < max; i++ )
    fprintf( fout, "%d ", pozsolfin[i] );

  fclose ( fin );
  fclose ( fout );

  return 0;
}