Cod sursa(job #2298590)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 decembrie 2018 11:34:57
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, x;
vector<long long> a, phi;

int kmp(vector<long long> x);

int main()
{
    f >> N;
    for(int i = 0; i < N; i++)
        f >> x, a.push_back(x);

    for(int i = 0; i < N - 1; i++)
        a[i] = a[i + 1] - a[i];
    a.pop_back();
    int s = kmp(a);
    g << s << "\n";
    for(int i = 0; i < s; i++)
        g << a[i] << "\n";
    return 0;
}

int kmp(vector<long long> x) {
    phi.resize(x.size(), 0);
    for(int i = 1; i < x.size(); i++) {
        int rez = phi[i - 1];
        while(rez && x[i] != x[rez])
            rez = phi[rez - 1];
        if(x[i] == x[rez]) rez++;
        phi[i] = rez;
    }
    return x.size() - phi[x.size() - 1];

}