Cod sursa(job #2317028)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 12 ianuarie 2019 18:19:20
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, x, aux[500003];
vector<long long> a, phi;

int kmp(vector<long long> x);

int main()
{
  f >> N;
  for(int i = 0; i < N; i++)
    f >> aux[i], a.emplace_back();

  for(int i = 1; i < N; i++)
    a[i - 1] = aux[i] - aux[i - 1];
  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++) {
    long long 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];

}