Cod sursa(job #3163517)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 31 octombrie 2023 15:45:53
Problema Reguli Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

int n;
vector <long long> v;
vector <int> pi;

void kmp()
{
    for(int i = 1; i < v.size(); i ++)
    {
        int j = pi[i - 1];
        while(j  &&  v[j] != v[i])
            j = pi[j - 1];
        if(v[i] == v[i])
            pi[i] = j + 1;
        else
            pi[i] = 0;
    }
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);

    cin >> n;

    long long a;
    cin >> a;

    for(int i = 1; i < n; i ++)
    {
        long long b;
        cin >> b;
        v.push_back(b - a);
        a = b;
    }

    pi.resize(v.size(), 0);

    kmp();

    int len = v.size() - pi.back();
    cout << len << "\n";
    for(int i = 0; i < len; i ++)
        cout << v[i] << "\n";
    return 0;
}