Cod sursa(job #794642)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 6 octombrie 2012 18:36:36
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>

using namespace std;

//ifstream in("strmatch.in");
//ofstream out("strmatch.out");

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

int t[600001],a[600001];
int k,pos,i,l,nr,n;

int main()
{
    in>>n;
    in>>l;
    for(i=1;i<n;i++)
    {
        in>>nr;
        a[i-1]=nr-l;
        l=nr;
    }
    //for(i=0;i<n-1;i++) out<<a[i]<<' ';
    //out<<"\n";
    t[0]=-1;
    t[1]=0;
    k=0;
    pos=2;
    l=1;
    while(pos<=n)
    {
        if(a[pos-1]==a[k])
                t[pos++]=++k;
        else
        {
            if(k!=0)
                k=t[k];
            else
                t[pos++]=0;
        }
    }
    //for(i=0;i<n;i++) out<<t[i]<<' ';
    //out<<"\n";
    n=n-1-t[n-1];
    out<<n<<"\n";
    for(i=0;i<n;i++) out<<a[i]<<"\n";
    return 0;
}