Cod sursa(job #2796093)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 7 noiembrie 2021 16:17:10
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;

vector<int> kmp(vector<ll> v) {
  reverse(v.begin(), v.end());
  v.push_back((ll)rand());
  reverse(v.begin(), v.end());
  int k = 0;
  vector<int> lps((int)v.size(), 0);
  for (int i = 2; i < (int)v.size(); i++) {
    while (k > 0 && v[k + 1] != v[i]) {
      k = lps[k];
    }
    if (v[k + 1] == v[i]) {
      k++;
    }
    lps[i] = k;
  }
  lps.erase(lps.begin());
  return lps;
}

int main() {
  in.tie(NULL);
  ios_base::sync_with_stdio(false);
  int n; in >> n;
  vector<ll> v(n);
  for (ll &x : v) {
    in >> x;
  }
  vector<ll> d(n - 1, 0);
  for (int i = 1; i < n; i++) {
    d[i - 1] = v[i] - v[i - 1];
  }
  auto lps = kmp(d);
  int result = n - 1 - lps.back();
  out << result << "\n";
  for (int i = 0; i < result; i++) {
    out << d[i] << "\n";
  }
  return 0;
}