Cod sursa(job #214359)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 13 octombrie 2008 22:50:34
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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 i = n;
    if(rez[n-1])
        for(i = n - 1; i > 1; --i)
            if((rez[i] - rez[i-1] != 1 && rez[i] == 1) || rez[i-1] == 0)
                break;
     fout<<i-1<<"\n";
    for(int k = 1; k < i; k++)
        fout<<sir[k]<<"\n";
}

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