Cod sursa(job #219144)

Utilizator dragosmihaiDragos Oana dragosmihai Data 5 noiembrie 2008 20:41:12
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>

using namespace std;

int n,a[500002],l,p[500002];

void citire();
void prefix();
void afisare();

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

void citire()
{
    ifstream f("reguli.in");
    f>>n;
    int x,y;
    f>>x;
    for(int i=1;i<n;i++)
    {
        f>>y;
        a[i]=y-x;
        x=y;
    }
    f.close();
}

void afisare()
{
    ofstream g("reguli.out");
    g<<l<<endl;
    for(int i=1;i<=l;i++)
        g<<a[i]<<endl;
    g.close();
}

void prefix()
{
    int k=0;
    for(int i=2;i<n;i++)
    {
        int ok=0;
        while(k&&a[k+1]!=a[i])
        {
            k=p[k];
            l=i;
            ok=1;
        }
        if(a[k+1]==a[i])
        {
            k++;
            if(ok&&i!=n-1)
                l--;
        }
        p[i]=k;
        if(k==0)
         l=i;
    }
}