Cod sursa(job #3163519)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 31 octombrie 2023 15:49:16
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 5e5;
int v[N], s[N], p[N];

int n;

void kmp () {
    int k = 0;
    for ( int i = 1; i < n; i++ ) {
        while ( k != 0 && s[k] != s[i] )
            k = p[k - 1];
        if ( s[k] == s[i] )
            k++;
        p[i] = k;
    }
}

int main () {
    
    fin >> n;
    
    for ( int i = 0; i < n; i++ )
        fin >> v[i];
    
    for ( int i = 0; i < n; i++ )
        s[i] = v[i + 1] - v[i];
    
    n--;
    kmp();
    
    int length = n - p[n - 1];
    
    fout << length << "\n";
    
    for ( int i = 0; i < length; i++ )
        fout << s[i] << "\n";
    
    return 0;
}