Cod sursa(job #2034869)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 8 octombrie 2017 15:37:20
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
//KMP
#include<fstream>
using namespace std;
ifstream fi("reguli.in");
ofstream fo("reguli.out");
int n,i,S[500001],k;
long long A[500001],pre,x;
int main()
{
    fi>>n;
    fi>>pre;
    for(i=1; i<=n; i++)
    {
        fi>>x;
        A[i]=x-pre;
        pre=x;
    }
    S[0]=-1;
    S[1]=0;
    for(i=1; i<n; i++)
    {
        k=i-1;
        while(S[k]!=-1 && A[S[k]+1]!=A[i])
            k=S[k];
        if(S[k]==-1)
            S[i]=0;
        else
            S[i]=S[k]+1;
    }
    //nr de perioade este egal cu distanta dintre ultimul lemming
    //si cel mai din dreapta lemming ramas in viata in cazul in care
    //ultimul cde in groapa
    fo<<n-1-S[n-1]<<"\n";
    for(i=1; i<=n-1-S[n-1]; i++)
        fo<<A[i]<<"\n";
    fi.close();
    fo.close();
    return 0;
}