Cod sursa(job #2141216)

Utilizator danutmafteiMaftei Danut danutmaftei Data 24 februarie 2018 11:12:51
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define Nmax 1000005

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

long long pre[Nmax],sir[Nmax],n,x,y;

void citire()
{
    fin>>n;

    fin>>x;
    n--;
    for(int i=1;i<=n;++i)
    {

        fin>>y;
        sir[i]=y-x;
        x=y;
    }
    fin.close();
}

void prefix()
{ int k=0;

    for(int i=2;i<=n;++i)
    {
        while(k>0 && sir[k+1]!=sir[i])
            k=pre[k];

            if(sir[k+1]==sir[i])++k;
            pre[i]=k;
    }
    fout<<n-pre[n]<<"\n";
    for(int i=1;i<=n-pre[n];++i)
        fout<<sir[i]<<"\n";
}




int main()
{
   citire();
   prefix();
    return 0;
}