Cod sursa(job #22595)

Utilizator magicMaria Ionescu magic Data 26 februarie 2007 21:18:51
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<iostream>
#include<fstream>

#define inputfile "reguli.in"
#define outputfile "reguli.out"

const int NMAX = 50000;

using namespace std;

void ReadData(int a[NMAX], int &N) {
  ifstream from(inputfile);
  from>>N;
  for (int i = 0; i<N; i++)
    from>>a[i];
  for (int i = N-1; i>0; i--)
    a[i] -= a[i-1];
  N--;
}

void FindMinSubstr(int a[NMAX], int N) {
  int p[NMAX];
  p[1] = 0;
  int k = 0;
  int min = 0;
  for (int q = 2; q<=N; q++) {
    while ( (k > 0) && ( a[k+1] != a[q])) {
      min = q - k;
      k = p[k];
    }
    if ( a[k+1] == a[q])
      k++;
    p[q] = k;
    if (k == 0) min = q - p[q];
  }
  ofstream to(outputfile);
  to<<min<<'\n';
  for (int i = 1; i<=min; i++) to<<a[i]<<'\n';
}

int main() {
  int a[NMAX];
  int N;
  ReadData(a,N);
  //  for (int i = 1; i<=N; i++) cout<<a[i]<<' '; cout<<'\n';
  FindMinSubstr(a,N);
}