Cod sursa(job #2518031)

Utilizator euyoTukanul euyo Data 4 ianuarie 2020 19:47:19
Problema Potrivirea sirurilor Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <stdio.h>
#include <ctype.h>
#define NH1 666013
#define NH2 666667
#define NR_ALPHABET 26
#define B 62
#define LIM 1000

int v[2000000], poz[1000];

int code( char c ) {
  int cod = 0;

  if ( c >= 'A' && c <= 'Z' ) {
    cod += c - 'A';
  } else if ( isdigit( c ) == 1 ) {
    cod += c - '0' + NR_ALPHABET * 2;
  } else {
    cod += c - 'a' + NR_ALPHABET;
  }
  return cod;
}

int main() {
  FILE *fin = fopen( "strmatch.in", "r" );
  FILE *fout = fopen( "strmatch.out", "w" );
  int i, ap, nA, hb1, hb2, pt1, pt2, h1, h2, st, dr;
  char c;

  c = fgetc( fin );
  h1 = h2 = nA = 0;
  pt1 = pt2 = 1;
  while ( c != '\n' ) {
    h1 = (h1 + code( c ) * pt1) % NH1;
    h2 = (h2 + code( c ) * pt2) % NH2;
    pt1 = (pt1 * B) % NH1;
    pt2 = (pt2 * B) % NH2;
    ++nA;
    c = fgetc( fin );
  }
  c = fgetc( fin );
  hb1 = hb2 = 0;
  pt1 = pt2 = 1;
  i = 0;
  while ( i < nA ) {
    hb1 = (hb1 + code( c ) * pt1) % NH1;
    hb2 = (hb2 + code( c ) * pt2) % NH2;
    pt1 = (pt1 * B) % NH1;
    pt2 = (pt2 * B) % NH2;
    v[i] = code( c );
    c = fgetc( fin );
    ++i;
  }
  ap = st = i = 0;
  dr = nA;
  while ( c != '\n' ) {
    if ( ap <= LIM ) {
      if ( h1 == hb1 && h2 == hb2 ) {
        poz[ap] = st;
        ++ap;
      }
    }
    hb1 = (((hb1 - v[st]) / B) + code( c ) * pt1) % NH1;
    hb2 = (((hb2 - v[st]) / B) + code( c ) * pt2) % NH2;
    //printf( "%d %d\n", hb1, hb2 );
    v[dr] = code( c );
    ++dr;
    ++st;
    c = fgetc( fin );
  }
  fprintf( fout, "%d\n", ap );
  for ( i = 0; i < ap; ++i ) {
    fprintf( fout, "%d ", poz[i] + 1 );
  }
  fclose( fin );
  fclose( fout );
  return 0;
}