Cod sursa(job #214348)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 13 octombrie 2008 22:40:01
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#define MAX 1000010

using namespace std;

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

long long sir[MAX],rez[MAX];
long long n,x,y,mx=1;

void citire()
{
     fin>>n;
     fin>>x;
     for (int i=1;i<n;i++)
     {
          fin>>y;
          sir[i]=y-x;
          x=y;
     }
     n--;
}
inline int maxx(int a,int b)
{
     return a>b?a:b;
}

void kmp()
{
     rez[1]=0;
     long long 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 k=n-1;
     mx=n;
     while (k>1)
     {
          if (rez[k-1]==0 || (rez[k]-rez[k-1]!=1 && rez[k]==1))
          {
               mx=k;
               break;
          }
          k--;
     }
     fout<<mx-1<<"\n";
     for (int j=1;j<mx;j++)
          fout<<sir[j]<<"\n";
}

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