Cod sursa(job #2298492)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 decembrie 2018 11:09:56
Problema Reguli Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#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;

}