Cod sursa(job #2148957)

Utilizator Y0da1NUME JMECHER Y0da1 Data 2 martie 2018 10:49:25
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>

#define maxn 500005
using namespace std;
int64_t A[maxn];
int64_t fail[maxn];
int N;

void kmp_fail()
{
    int64_t j = 0;
    for (int64_t i = 1; i < N; ++i)
    {
        while(A[i] != A[j] && j > 0)
            j = fail[j - 1];
        if(A[i] == A[j])
            ++j;
        fail[i] = j;
    }
}

void afis()
{
    for (int i = 0; i < N; ++i)
        cout<<A[i]<<" ";
    cout<<"\n";

    for (int i = 0; i < N; ++i)
        cout<<fail[i]<<" ";
    cout<<"\n";
}
int main()
{
    ifstream in ("reguli.in");
    ofstream out ("reguli.out");
    int64_t x, y;
    in>>N;
    in>>x;
    for(int i = 1; i < N; ++i)
    {
        in>>y;
        A[i - 1] = y - x;
        x = y;
    }
    --N;
    //cout<<N<<"\n";
    kmp_fail();
    //afis();

    out<<N - fail[N-1]<<"\n";
    for(int i = 0; i < N - fail[N - 1]; ++i)
        out<<A[i]<<"\n";
    return 0;
}