Cod sursa(job #214068)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 12 octombrie 2008 15:51:20
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#define MAX 500100

using namespace std;

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

int sir[MAX],rez[MAX];
int n,x,y,mx;

void citire()
{
     fin>>n;
     fin>>x;
     for (int i=0;i<n-1;i++)
     {
          fin>>y;
          sir[i]=y-x;
          x=y;
     }
}

void kmp()
{
     rez[1]=0;
     int p=0;
     for (int i=2;i<n;i++)
     {
          while (p && sir[p+1]!=sir[i])
               p=rez[p];

          if (sir[p+1]==sir[i])
               p++;

          rez[i]=p;
     }
}
void afisare()
{
     int i=n-2;
     while (rez[i])
          i--;
     fout<<i<<"\n";
     for (int j=0;j<i;j++)
          fout<<sir[j]<<"\n";
}

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