Cod sursa(job #1932417)

Utilizator darian2001Clodnischi Darian Antonio darian2001 Data 19 martie 2017 19:20:33
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
using namespace std;

ifstream f("reguli.in");
ofstream g("reguli.out");

long long n,sir[500000];
long long pi[500000];

void KMP()
{
    int j=0,elemMax=n;
    for(int i=1;i<n;i++)
    {
        while(j>0&&sir[i]!=sir[j])
            j=pi[j-1];
        if(sir[i]==sir[j])
            j++;
        pi[i]=j;
    }

    elemMax=elemMax-pi[n-1];
    g<<elemMax<<"\n";


    for(int i=0;i<elemMax;i++)
        g<<sir[i]<<"\n";
}

int main()
{
    f>>n;
    long long first,nr;
    f>>first;n--;
    for(int i=0;i<n;i++)
    {
        f>>nr;
        sir[i]=nr-first;

        first=nr;
    }
    KMP();
    f.close();
    g.close();
}