Mai intai trebuie sa te autentifici.

Cod sursa(job #1978846)

Utilizator TincaMateiTinca Matei TincaMatei Data 8 mai 2017 22:29:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <ctype.h>

const int MAX_N = 2000000;
char sir[MAX_N+1+MAX_N];
int d[MAX_N+1+MAX_N];

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

int rez[1000];

int main() {
  int n1, n2, st, dr, top = 0;
  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)) {
    sir[n1+n2] = ch;
    ++n2;
    ch = getch(fin);
  }
  fclose(fin);

  d[0] = 1;
  st = dr = 0;
  for(int i = 1; i < n1 + 1 + n2; ++i) {
    if(i > dr) {
      d[i] = 0;
      while(sir[d[i]] == sir[i+d[i]])
        ++d[i];
      st = i;
    }
    if(i < dr) {
      d[i] = d[i - st];
      if(i + d[i] >= dr) {
        d[i] = dr - i + 1;
        st = i;
        while(sir[d[i]] == sir[i+d[i]])
          ++d[i];
        dr = st + d[i] - 1;
      }
    }
    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;
}