Cod sursa(job #2140850)

Utilizator SineMineSzasz Bogdan SineMine Data 23 februarie 2018 22:16:33
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int Nmax = 500004;

int N;
long long S[Nmax];
int KMP[Nmax];

int main()
{
    fin >> N;
long long x, y;
    fin >> x;
for (int i = 1; i < N; ++i)
    {
        fin >> y;
        S[i] = y-x;
        x = y;
    }

for (int i = 2, k = 0; i < N; ++i)
    {
    while (k > 0 && S[k+1] != S[i])
        k = KMP[k];
    if (S[k+1] == S[i])
        ++k;
        KMP[i] = k;
    }

fout << N - KMP[N - 1] - 1 << '\n';
for (int i = 1; i < N - KMP[N - 1]; ++i)
    fout << S[i] << '\n';

fin.close();
fout.close();
}