Cod sursa(job #1379374)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 6 martie 2015 17:37:54
Problema Reguli Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 500000

long long x[MAX_N], a[MAX_N];
int pi[MAX_N];

void KMP(int n) {
  int i, k = 0;
  pi[0] = 0;

  for (i = 1; i < n - 1; i++) {
    while (k > 0 && a[i] != a[k]) {
      k = pi[k - 1];
    }
    if (a[i] == a[k]) {
      k++;
    }
    pi[i] = k;
  }
}


int main()
{
  FILE *in  = fopen("reguli.in", "r");
  FILE *out = fopen("reguli.out", "w");

  int n, i;
  fscanf(in, "%d", &n);
  for (i = 0; i < n; i++) {
    fscanf(in, "%lld", &x[i]);
    if (i >= 1) {
      a[i - 1] = x[i] - x[i - 1];
    }
  }

  KMP(n);
  int rez = (n - 1) - pi[n - 2];

  fprintf(out, "%d\n", rez);
  for (i = 0; i < rez; i++)
    fprintf(out, "%lld\n", a[i]);

  return 0;
}