Cod sursa(job #214142)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 12 octombrie 2008 22:42:19
Problema Reguli Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#define MAX 1000010

using namespace std;

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

long long 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+1]=y-x;
          x=y;
     }
     n--;
}

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;
     while (rez[i]!=0 && rez[i]>rez[i-1])
     {
          i--;
     }
     fout<<i<<"\n";
     for (int j=1;j<=i;j++)
          fout<<sir[j]<<"\n";
}

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