Cod sursa(job #2461775)

Utilizator deiubejanAndrei Bejan deiubejan Data 26 septembrie 2019 09:46:19
Problema Reguli Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;

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

#define cin fin
#define cout fout
/*
*/


const int NMAX=6e5;
int n;
int x[NMAX];
int pas[NMAX];
int lps[NMAX];

void read()
{
    int x_;
    cin>>n;
    cin>>x_>>x[0];
    pas[0]=x[0]-x_;
    for(int i=2; i<n; i++)
    {
        cin>>x[i-1];
        pas[i-1]=x[i-1]-x[i-2];
    }
    n--;
}

void computeLPS()
{
    lps[0]=0;
    int len=0, i=1;
    while(i<n)
    {
        if(pas[i]==pas[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if(len!=0)
                len=lps[len-1];
            else
            {
                lps[i]=0;
                i++;
            }
        }

    }
}

void solve()
{
    computeLPS();
    int i=1, j=0, len=1;
    while(i<n)
    {
        if(pas[i]==pas[j])
        {
            i++;
            j++;
            if(j==len)
                j=0;
        }
        else
        {
            if(j!=0)
                j=lps[j-1];
            else
            {
                i++;
                len=i;
            }

        }
    }
    cout<<len<<"\n";
    for(int i=0; i<len; i++)
        cout<<pas[i]<<"\n";
}




int main()
{
    read();
    solve();


    return 0;
}