Cod sursa(job #1979175)

Utilizator TincaMateiTinca Matei TincaMatei Data 9 mai 2017 20:39:27
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <ctype.h>

const int MAX_N = 2000000;
const int BUFF = 4096;
char sir[MAX_N+1+MAX_N];
int curs = BUFF - 1;
int d[MAX_N+1+MAX_N];

char buff[BUFF];

char nextch(FILE *fin) {
  ++curs;
  if(curs == BUFF) {
    curs = 0;
    fread(buff, 1, BUFF, fin);
  }
  return buff[curs];
}

char getch(FILE *fin) {
  char ch = nextch(fin);
  while(ch == ' ')
    ch = nextch(fin);
  return ch;
}

int rez[1000];

int main() {
  int n1, n2, st, dr, top = 0, n3;
  FILE *fin = fopen("strmatch.in", "r");
  n1 = n2 = 0;
  char ch = getch(fin);
  while(isalpha(ch) || isdigit(ch)) {
    sir[n1++] = ch;
    ch = getch(fin);
  }
  ch = getch(fin);
  while(isalpha(ch) || isdigit(ch)) {
    ++n2;
    sir[n1+n2] = ch;
    ch = getch(fin);
  }
  fclose(fin);
  n3 = n1 + 1 + n2;

  d[0] = 0;
  st = dr = 0;
  for(int i = 1; i < n3; ++i) {
    d[i] = d[i - st];
    if(i + d[i] >= dr - 1) {
      d[i] = dr - i;
      if(d[i] < 0)
        d[i] = 0;
      st = i;
      dr = i + d[i];
    }
    while(i + d[i] < n3 && sir[d[i]] == sir[i + d[i]]) {
      ++d[i];
      ++dr;
    }

    if(d[i] == n1) {
      if(top < 1000)
        rez[top] = i - n1 - 1;
      top++;
    }
  }

  FILE *fout = fopen("strmatch.out", "w");
  fprintf(fout, "%d\n", top);
  for(int i = 0; i < top && i < 1000; ++i)
    fprintf(fout, "%d ", rez[i]);
  fclose(fout);
  return 0;
}