Cod sursa(job #1518308)

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

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

char getChar ( char a ) {
  if ( a >= 'A' && a <= 'Z' )
    return a - 'A' + 1;
  else if ( a >= 'a' && a <= 'z' )
    return a - 'a' + 27;
  else /// a >= '0' && a <= '9'
    return a - '0' + 53;
}

int pass ( int num, int nxtchr, int x ) { /// sterg ultima cifra si o adaug pe urmatoarea
  int p63 = 1;

  while ( p63 * 63 <= num )
    p63 *= 63;

  num %= p63; /// elimin prima cifra -- num = num - ( num / p63 ) * p63;

  return ( num * 63 + getChar( nxtchr ) ) % modval[x];
}

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

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

  fgets ( v1, MAXLEN, fin ); /// string to be searched
  fgetc ( fin ); /// '\n'
  fgets ( v2, MAXLEN, fin ); /// string to search inside

  int MODcount, i, len = strlen ( v1 ), len2 = strlen( v2 ), p63 = 1, num1, num2; /// num to be searched;
  int cnt, max = 0; /// counter, nr. maxim al contorului, pozitia lui

  len -= 2; len2 -= 2;

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

    p63 = 1;

    for ( i = len - 1; i >= 0; i--, p63 *= 63, num1 %= modval[MODcount] )
      num1 += ( p63 * getChar( v1[i] ) ) % modval[MODcount];

    num1 %= modval[MODcount];

    p63 = 1;
    for ( i = len - 1; i >= 0; i--, p63 *= 63, num2 %= modval[MODcount] )
      num2 += ( p63 * getChar( v2[i] ) ) % modval[MODcount];

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

      num2 = pass ( num2, v2[i], MODcount );
    }

    fvind[cnt]++;

    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;
}