Cod sursa(job #1904554)

Utilizator ReksioCroftOctavian Florin Staicu ReksioCroft Data 5 martie 2017 17:15:52
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <string.h>
using namespace std;
#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;
ifstream fin( "date.in" );
ofstream fout( "date.out" );
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 );
  */
  fin >> v[0] >> v[1];
  poza = strlen( v[0] );
  pozb = strlen( v[1] );
  preinitializare_pi();
  kmp();
  //fout = fopen( "strmatch.out", "w" );
  //fprintf( fout, "%d\n", co );
  fout << co << '\n';
  for ( i = 0; i < poz_ans; i++ )
    //fprintf( fout, "%d ", ans[i] );
    fout << ans[i] << " ";
  //fputc( '\n', fout );
  fout << "\n";
  //fclose( fout );
  fin.close();
  fout.close();
  return 0;
}