Cod sursa(job #2637296)

Utilizator andreic06Andrei Calota andreic06 Data 22 iulie 2020 13:01:47
Problema Reguli Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>

using namespace std;
const int N = 5e5;
int dif[N+1], lps[N];

ifstream fin ( "reguli.in" );
ofstream fout ( "reguli.out" );

int n;
int x, y;
void process_prefix () {
    int len = 0;
    lps[0] = 0;

    for ( int i = 1; i < n; i ++ ) {
       while ( len > 0 && dif[len] == dif[i] )
          len = lps[len-1];
      if ( dif[len] == dif[i] )
        len ++;
      lps[i] = len;
    }
}
int main()
{
   fin >> n;
   fin >> x;
   for ( int i = 1; i < n; i ++ ) {
     fin >> y, dif[i-1] = y - x;
     x = y;
   }
   n --;
   process_prefix ();

   int i = 0;
   while ( i < n && lps[i] == 0 )
      i ++;
   fout << i << '\n';
   for ( int j = 0; j < i; j ++ )
      fout << dif[j] << '\n';
    return 0;
}