Cod sursa(job #1904552)

Utilizator ReksioCroftOctavian Florin Staicu ReksioCroft Data 5 martie 2017 17:09:58
Problema Potrivirea sirurilor Scor 62
Compilator c Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>
#include <ctype.h>

#define buff_size 1<<17
#define nmax 2000001
#define ansmax 1000

char buffer[buff_size];
int poz_buff = buff_size;
FILE *fin, *fout;
int poza, pozb, poz_ans;
char v[2][nmax];
int pi[nmax];
int ans[ansmax];
int co;

char getch() {
  if ( poz_buff == buff_size ) {
    poz_buff = 0;
    fread( buffer, 1, buff_size, fin );
  }
  return buffer[ poz_buff++ ];
}

void preinitializare_pi() {
  int lung, i;
  lung = 0;
  for ( i = 2; i <= poza; i++ ) {
    while ( lung > 0 && v[0][ lung + 1 ] != v[0][i] )
      lung = pi[lung];
    if ( v[0][ lung + 1 ] == v[0][i] )
      lung++;
    pi[i] = lung;
  }
}

void kmp() {
  int lung, i;
  lung = 0;
  for ( i = 1; i <= pozb; i++ ) {
    while ( lung > 0 && v[0][ lung + 1 ] != v[1][i] )
      lung = pi[lung];
    if ( v[0][ lung + 1 ] == v[1][i] )
      lung++;
    if ( lung == poza ) {
      co++;
      if ( poz_ans < ansmax ) {
        ans[poz_ans] = i - poza;
        poz_ans++;
      }
      lung = pi[lung];
    }
  }
}

int main() {
  int i;
  char ch;
  fin = fopen( "strmatch.in", "r" );
  ch = getch();
  while ( isalpha(ch) != 0 ) {
    v[0][++poza] = ch;
    ch = getch();
  }
  ch = getch();
  while ( isalpha(ch) != 0 ) {
    v[1][++pozb] = ch;
    ch = getch();
  }
  fclose( fin );
  preinitializare_pi();
  kmp();
  fout = fopen( "strmatch.out", "w" );
  fprintf( fout, "%d\n", co );
  for ( i = 0; i < poz_ans; i++ )
    fprintf( fout, "%d ", ans[i] );
  fputc( '\n', fout );
  fclose( fout );
  return 0;
}