Pagini recente » Cod sursa (job #332876) | Cod sursa (job #3223799) | Cod sursa (job #1557953) | Cod sursa (job #3128771) | Cod sursa (job #2298492)
#include <bits/stdc++.h>
using namespace std;
ifstream f("reguli.in");
ofstream g("reguli.out");
int N, x;
vector<int> a, phi;
int kmp(vector<int> 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 dr = kmp(a), st = dr + 1;
g << phi[dr] << "\n";
for(st = dr; phi[st] != 1; st--);
for(int i = st; i <= dr; i++)
g << a[i] << "\n";
return 0;
}
int kmp(vector<int> x) {
int MAX = 0;
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;
if(((i + 1) - phi[i]) < (i + 1) && (i + 1) % ((i + 1) - phi[i]) == 0)
MAX = i;
}
return MAX;
}