Pagini recente » Cod sursa (job #99919) | Cod sursa (job #1473411) | Cod sursa (job #2938619) | Cod sursa (job #3132561) | Cod sursa (job #2796093)
#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;
}